Submission #2233697
Source Code Expand
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <tuple>
# include <unordered_map>
# include <numeric>
# include <complex>
# include <bitset>
# include <random>
# include <chrono>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
typedef pair<LL, LL> P;
constexpr int INF = 2000000000;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
# define ALL(x) (x).begin(),(x).end()
# define UNIQ(c) (c).erase(unique(ALL((c))),(c).end())
# define mp make_pair
# define eb emplace_back
# define FOR(i,a,b) for(int i=(a);i<(b);i++)
# define RFOR(i,a,b) for(int i=(a);i>=(b);i--)
# define REP(i,n) FOR(i,0,n)
# define INIT std::ios::sync_with_stdio(false);std::cin.tie(0)
const int MAX_V = 101010;
struct edge { int to, cap, rev; };
vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];
void add_edge(int from, int to, int cap) {
G[from].emplace_back(edge{ to,cap,(int)G[to].size() });
G[to].emplace_back(edge{ from,0,(int)G[from].size() - 1 });
}
void bfs(int s) {
REP(i, MAX_V)level[i] = -1;
queue<int> que;
level[s] = 0;
que.push(s);
while (!que.empty()) {
int v = que.front();
que.pop();
REP(i, G[v].size()) {
edge &e = G[v][i];
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
que.push(e.to);
}
}
}
}
int dfs(int v, int t, int f) {
if (v == t)return f;
for (int &i = iter[v]; i < G[v].size(); i++) {
edge &e = G[v][i];
if (e.cap > 0 && level[v] < level[e.to]) {
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 max_flow(int s, int t) {
int flow = 0;
for (;;) {
bfs(s);
if (level[t] < 0)return flow;
REP(i, MAX_V)iter[i] = 0;
int f;
while ((f = dfs(s, t, INF)) > 0) {
flow += f;
}
}
}
int n, m, p, g;
int l;
int main() {
int s = 1234;
cin >> n >> m >> p >> g;
REP(i, g) {
cin >> l;
add_edge(s, l, HINF);
}
REP(i, n) {
int a, b, c;
cin >> a >> b >> c;
add_edge(a, b, c);
}
cout << (max_flow(s, 0)>=p?"Yes":"No") << endl;
}
Submission Info
Submission Time |
|
Task |
H - お風呂は気持ちいい |
User |
M3_cp |
Language |
C++14 (GCC 5.4.1) |
Score |
140 |
Code Size |
2596 Byte |
Status |
AC |
Exec Time |
3 ms |
Memory |
3456 KB |
Judge Result
Set Name |
f1t |
basic |
Score / Max Score |
40 / 40 |
100 / 100 |
Status |
|
|
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 |
3 ms |
3456 KB |
sample01 |
AC |
2 ms |
3072 KB |
sample02 |
AC |
2 ms |
3456 KB |
basic/basic_case00 |
AC |
3 ms |
3456 KB |
basic/basic_case01 |
AC |
3 ms |
3456 KB |
basic/basic_case02 |
AC |
3 ms |
3456 KB |
basic/basic_case03 |
AC |
3 ms |
3456 KB |
basic/basic_case04 |
AC |
3 ms |
3456 KB |
basic/basic_case05 |
AC |
3 ms |
3456 KB |
basic/basic_case06 |
AC |
3 ms |
3456 KB |
basic/basic_case07 |
AC |
3 ms |
3456 KB |
basic/basic_case08 |
AC |
3 ms |
3456 KB |
basic/basic_case09 |
AC |
2 ms |
3456 KB |
basic/corner00 |
AC |
2 ms |
3072 KB |
basic/sample00 |
AC |
3 ms |
3456 KB |
basic/sample01 |
AC |
2 ms |
3072 KB |
basic/sample02 |
AC |
2 ms |
3456 KB |
f1t/basic_case00 |
AC |
2 ms |
3456 KB |
f1t/basic_case01 |
AC |
3 ms |
3456 KB |
f1t/basic_case02 |
AC |
3 ms |
3456 KB |
f1t/basic_case03 |
AC |
2 ms |
3456 KB |
f1t/basic_case04 |
AC |
2 ms |
3456 KB |
f1t/basic_case05 |
AC |
3 ms |
3456 KB |
f1t/basic_case06 |
AC |
3 ms |
3456 KB |
f1t/basic_case07 |
AC |
2 ms |
3456 KB |
f1t/basic_case08 |
AC |
3 ms |
3456 KB |
f1t/basic_case09 |
AC |
3 ms |
3456 KB |
f1t/sample00 |
AC |
3 ms |
3456 KB |
f1t/sample01 |
AC |
2 ms |
3072 KB |
f1t/sample02 |
AC |
3 ms |
3456 KB |