Submission #1444440


Source Code Expand

#include "bits/stdc++.h"
using namespace std;

struct edge {
        int to, cap, rev;
};
bool used[101010];
vector<edge> g[101010];
static const int INF = 0x3f3f3f3f;
void add_edge(int from, int to, int cap) {
        g[from].push_back((edge) { to, cap, (int)g[to].size() });
        g[to].push_back((edge) { from, 0, (int)g[from].size() - 1 });
}
int dfs(int v, int t, int f) {
        if (v == t) return f;
        used[v] = true;
        for (int i = 0; i < g[v].size(); i ++) {
                edge& e = g[v][i];
                if (!used[e.to] && e.cap > 0) {
                        int d = dfs(e.to, t, min(f, e.cap));
                        if (d > 0) {
                                e.cap -= d;
                                g[e.to][e.rev].cap += d;
                                return  d;
                        }
                }
        }
        return 0;
}
int MaxFlow(int s, int t) {
        int flow = 0;
        while (true) {
                memset(used, false, sizeof(used));
                int f = dfs(s, t, INF);
                if (f == 0) return flow;
                flow += f;
        }
}

int main() {
        int n, m, p, g;
        cin >> n >> m >> p >> g;
        int s = m, t = 0;
        for (int i = 0; i < g; i ++) {
                int l;
                cin >> l;
                add_edge(s, l, INF);
        }
        for (int i = 0; i < n; i ++) {
                int a, b, c;
                cin >> a >> b >> c;
                add_edge(a, b, c);
        }
        int ans = MaxFlow(s, t);
        if (ans < p) cout << "No" << endl;
        else cout << "Yes" << endl;
        return 0;
}

Submission Info

Submission Time
Task H - お風呂は気持ちいい
User KokiYmgch
Language C++14 (GCC 5.4.1)
Score 140
Code Size 1699 Byte
Status AC
Exec Time 5 ms
Memory 2688 KB

Judge Result

Set Name f1t basic
Score / Max Score 40 / 40 100 / 100
Status
AC × 13
AC × 14
Set Name Test Cases
f1t f1t/basic_case00, f1t/basic_case01, f1t/basic_case02, f1t/basic_case03, f1t/basic_case04, f1t/basic_case05, f1t/basic_case06, f1t/basic_case07, f1t/basic_case08, f1t/basic_case09, f1t/sample00, f1t/sample01, f1t/sample02
basic basic/basic_case00, basic/basic_case01, basic/basic_case02, basic/basic_case03, basic/basic_case04, basic/basic_case05, basic/basic_case06, basic/basic_case07, basic/basic_case08, basic/basic_case09, basic/corner00, basic/sample00, basic/sample01, basic/sample02
Case Name Status Exec Time Memory
sample00 AC 2 ms 2688 KB
sample01 AC 2 ms 2688 KB
sample02 AC 2 ms 2688 KB
basic/basic_case00 AC 3 ms 2688 KB
basic/basic_case01 AC 5 ms 2688 KB
basic/basic_case02 AC 3 ms 2688 KB
basic/basic_case03 AC 3 ms 2688 KB
basic/basic_case04 AC 4 ms 2688 KB
basic/basic_case05 AC 2 ms 2688 KB
basic/basic_case06 AC 2 ms 2688 KB
basic/basic_case07 AC 3 ms 2688 KB
basic/basic_case08 AC 3 ms 2688 KB
basic/basic_case09 AC 3 ms 2688 KB
basic/corner00 AC 2 ms 2688 KB
basic/sample00 AC 2 ms 2688 KB
basic/sample01 AC 2 ms 2688 KB
basic/sample02 AC 2 ms 2688 KB
f1t/basic_case00 AC 2 ms 2688 KB
f1t/basic_case01 AC 2 ms 2688 KB
f1t/basic_case02 AC 2 ms 2688 KB
f1t/basic_case03 AC 2 ms 2688 KB
f1t/basic_case04 AC 2 ms 2688 KB
f1t/basic_case05 AC 2 ms 2688 KB
f1t/basic_case06 AC 2 ms 2688 KB
f1t/basic_case07 AC 2 ms 2688 KB
f1t/basic_case08 AC 2 ms 2688 KB
f1t/basic_case09 AC 2 ms 2688 KB
f1t/sample00 AC 2 ms 2688 KB
f1t/sample01 AC 2 ms 2688 KB
f1t/sample02 AC 2 ms 2688 KB