Submission #1260321

#TimeUsernameProblemLanguageResultExecution timeMemory
1260321anteknneGraph (BOI20_graph)C++20
0 / 100
2 ms2628 KiB
#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; typedef long long ll; typedef long double ld; #define pb push_back #define pii pair<int, int> #define pll pair<ll, ll> #define st first #define nd second #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> #define debug false const int MAXN = 100 * 1000 + 17; const int INF = 100 * 1000 * 1000; vector<pii> graf[MAXN]; int c[MAXN]; int C[MAXN]; bool odw[MAXN]; bool ODW[MAXN]; vector<int> vec; vector<int> kand = {1000 * 1000, 500 * 1000, 0, -1000 * 1000, -500 * 1000, 2000 * 1000, -2000 * 1000}; int n; void DFS (int v) { vec.pb(v); for (auto x : graf[v]) { if (!odw[x.st]) { odw[x.st] = true; c[x.st] = x.nd - c[v]; DFS(x.st); } } } bool licz (int v, int x) { vec.clear(); c[v] = x; odw[v] = true; DFS(v); for (int i = 1; i <= n; i ++) { for (auto x : graf[i]) { if (c[i] + c[x.st] != x.nd) { return false; } } } return true; } int main () { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int m; cin >> n >> m; int a, b, r; for (int i = 0; i < m; i ++) { cin >> a >> b >> r; if (a == b) { r *= 2; } graf[a].pb({b, r * 1000 * 1000}); graf[b].pb({a, r * 1000 * 1000}); } int cnt = 0; for (int i = 1; i <= n; i ++) { c[i] = INF; } for (int v = 1; v <= n; v ++) { if (int(graf[v].size()) == 0) { ODW[v] = true; cnt ++; C[v] = 0; continue; } if (ODW[v]) { continue; } for (auto i : kand) { if (ODW[v]) { break; } if (licz(v, i)) { for (auto x : vec) { ODW[x] = true; C[x] = c[x]; cnt ++; } } for (auto x : vec) { c[x] = INF; odw[x] = false; } } } if (cnt == n) { cout << "YES\n"; for (int i = 1; i <= n; i ++) { cout << ld(C[i])/ld(1000 * 1000) << " "; } cout << "\n"; } else { cout << "NO\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...