Submission #1721125
Source Code Expand
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define fi first #define se second #define mp make_pair #define pb push_back #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<ll,ll> ii; typedef vector<int> vi; typedef long double ld; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; typedef set<int>::iterator sit; typedef map<int,int>::iterator mit; typedef vector<int>::iterator vit; ll a[100001][2]; vector<ii> adj[100001][2]; bool visited[100001][2]; const ll INF = ll(1e18); const ll INF2 = ll(1e15); ii relax(ii x, ii y) { return mp(min(x.fi, y.fi), min(x.se, y.se)); } ii dfs(int u, bool s) { ii ans = mp(INF, INF); for(int i = 0; i < adj[u][s].size(); i++) { int v = adj[u][s][i].fi; ll w = adj[u][s][i].se; //cerr << v << ' ' << w << '\n'; if(a[v][(s^1)] != -1) { if(a[v][(s^1)] + a[u][s] != w) return mp(-1, -1); if(s) ans = relax(ans, mp(a[v][(s^1)], a[u][s])); else ans = relax(ans, mp(a[u][s], a[v][(s^1)])); } else { a[v][(s^1)] = w - a[u][s]; //cerr << v << ' ' << (s^1) << ' ' << a[v][(s^1)] << '\n'; ii tmp = dfs(v, (s^1)); ans = relax(ans, tmp); } } return ans; } void dfs2(int u, bool s, ll shift) { visited[u][s] = true; for(int i = 0; i < adj[u][s].size(); i++) { int v = adj[u][s][i].fi; if(visited[v][(s^1)]) continue; else { if(s) a[v][(s^1)] -= shift; else a[v][(s^1)] += shift; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int R, C, n; cin>>R>>C>>n; memset(a, -1, sizeof(a)); ll a0 = 0; bool forced = false; for(int i = 0; i < n; i++) { int x, y; ll val; cin>>x>>y>>val; if(x == 1 && y == 1) { a0 = val; forced = true; } adj[x][0].pb(mp(y, val)); adj[y][1].pb(mp(x, val)); //ma[ii(x, y)] = val; //vec.pb(ii(x, y)); } /* a[1][0] = a0; a[1][1] = a0; for(int i = 1; i <= max(R, C); i++) { for(int j = 0; j < 2; j++) { if(i > R && j == 0) continue; if(i > C && j == 1) continue; for(int k = 0; k < adj[i][j].size(); k++) { adj[i][j][k].se += a0; } } } */ for(int i = 1; i <= max(R, C); i++) { for(int j = 0; j < 2; j++) { if(i > R && j == 0) continue; if(i > C && j == 1) continue; if(a[i][j] == -1) a[i][j] = 0; ii tmp = dfs(i, j); //cerr << i << ' ' << j << ' ' << tmp.fi << ' ' << tmp.se << '\n'; /* if(i == 1 && forced) { if(tmp.fi < 0 || tmp.se < 0) { cout << "No\n"; return 0; } } */ if(1) { if(tmp.fi + tmp.se < 0) { cout << "No\n"; return 0; } /* else if(tmp.fi < 0 || tmp.se < 0) { ll shift = 0; if(tmp.fi < 0) shift = -tmp.fi; else shift = tmp.se; //cerr << tmp.fi << ' ' << tmp.se << ' ' << shift << '\n'; dfs2(i, j, shift); } */ } } } /* for(int i = 1; i <= max(R, C); i++) { for(int j = 0; j < 2; j++) { if(i > R && j == 0) continue; if(i > C && j == 1) continue; cerr << i << ' ' << j << ' ' << a[i][j] << '\n'; } } */ for(int i = 1; i <= R; i++) { if(a[i][0] == -1) a[i][0] = INF2; } for(int i = 1; i <= C; i++) { if(a[i][1] == -1) a[i][1] = INF2; } ll mina = INF; ll minb = INF; /* for(int i = 1; i <= R; i++) mina = min(mina, a[i][0]); for(int i = 1; i <= C; i++) minb = min(minb, a[i][1]); */ if(mina + minb >= a0) cout << "Yes\n"; else cout << "No\n"; }
Submission Info
Submission Time | |
---|---|
Task | D - Grid and Integers |
User | vjudge3 |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 3492 Byte |
Status | AC |
Exec Time | 62 ms |
Memory | 21120 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 800 / 800 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt |
All | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt, 1_56.txt, 1_57.txt, 1_58.txt, 1_59.txt, 1_60.txt, 1_61.txt, 1_62.txt, 1_63.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_00.txt | AC | 3 ms | 6528 KB |
0_01.txt | AC | 3 ms | 6528 KB |
0_02.txt | AC | 3 ms | 6528 KB |
0_03.txt | AC | 3 ms | 6528 KB |
0_04.txt | AC | 3 ms | 6528 KB |
1_00.txt | AC | 4 ms | 6528 KB |
1_01.txt | AC | 4 ms | 6528 KB |
1_02.txt | AC | 4 ms | 6528 KB |
1_03.txt | AC | 3 ms | 6528 KB |
1_04.txt | AC | 4 ms | 6528 KB |
1_05.txt | AC | 3 ms | 6528 KB |
1_06.txt | AC | 47 ms | 12800 KB |
1_07.txt | AC | 53 ms | 12800 KB |
1_08.txt | AC | 50 ms | 12032 KB |
1_09.txt | AC | 45 ms | 12032 KB |
1_10.txt | AC | 58 ms | 11776 KB |
1_11.txt | AC | 52 ms | 11776 KB |
1_12.txt | AC | 62 ms | 21120 KB |
1_13.txt | AC | 60 ms | 21120 KB |
1_14.txt | AC | 62 ms | 21120 KB |
1_15.txt | AC | 59 ms | 21120 KB |
1_16.txt | AC | 56 ms | 17280 KB |
1_17.txt | AC | 57 ms | 20736 KB |
1_18.txt | AC | 55 ms | 19328 KB |
1_19.txt | AC | 55 ms | 17664 KB |
1_20.txt | AC | 34 ms | 11520 KB |
1_21.txt | AC | 17 ms | 8064 KB |
1_22.txt | AC | 5 ms | 6784 KB |
1_23.txt | AC | 34 ms | 9856 KB |
1_24.txt | AC | 41 ms | 12672 KB |
1_25.txt | AC | 33 ms | 10880 KB |
1_26.txt | AC | 6 ms | 6912 KB |
1_27.txt | AC | 9 ms | 7168 KB |
1_28.txt | AC | 51 ms | 13696 KB |
1_29.txt | AC | 19 ms | 8320 KB |
1_30.txt | AC | 47 ms | 12544 KB |
1_31.txt | AC | 22 ms | 8576 KB |
1_32.txt | AC | 41 ms | 12672 KB |
1_33.txt | AC | 49 ms | 12544 KB |
1_34.txt | AC | 9 ms | 7168 KB |
1_35.txt | AC | 41 ms | 10880 KB |
1_36.txt | AC | 13 ms | 7296 KB |
1_37.txt | AC | 22 ms | 9600 KB |
1_38.txt | AC | 39 ms | 10240 KB |
1_39.txt | AC | 14 ms | 7680 KB |
1_40.txt | AC | 38 ms | 10112 KB |
1_41.txt | AC | 20 ms | 8320 KB |
1_42.txt | AC | 45 ms | 13056 KB |
1_43.txt | AC | 30 ms | 9856 KB |
1_44.txt | AC | 40 ms | 11776 KB |
1_45.txt | AC | 14 ms | 7936 KB |
1_46.txt | AC | 46 ms | 12288 KB |
1_47.txt | AC | 18 ms | 8448 KB |
1_48.txt | AC | 16 ms | 8064 KB |
1_49.txt | AC | 8 ms | 7040 KB |
1_50.txt | AC | 27 ms | 9728 KB |
1_51.txt | AC | 51 ms | 13824 KB |
1_52.txt | AC | 7 ms | 6912 KB |
1_53.txt | AC | 11 ms | 7296 KB |
1_54.txt | AC | 18 ms | 8064 KB |
1_55.txt | AC | 22 ms | 8832 KB |
1_56.txt | AC | 34 ms | 10624 KB |
1_57.txt | AC | 52 ms | 14336 KB |
1_58.txt | AC | 42 ms | 11904 KB |
1_59.txt | AC | 6 ms | 6784 KB |
1_60.txt | AC | 3 ms | 6528 KB |
1_61.txt | AC | 3 ms | 6528 KB |
1_62.txt | AC | 3 ms | 6528 KB |
1_63.txt | AC | 3 ms | 6528 KB |