Submission #650567

#TimeUsernameProblemLanguageResultExecution timeMemory
650567welleythGraph (BOI20_graph)C++17
0 / 100
28 ms51540 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; #define int long long #define pb push_back #define mp make_pair #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx2") constexpr int N = (int)(1 << 21); constexpr int md = (int)2e5 + 111; constexpr int INF = (int)1e18 + 111; constexpr int K = (int)30; mt19937 rnd(time(nullptr)); bool used[N]; int val[N]; vector<pair<int,int>> g[N]; bool can = true; int S = 0; void dfs(int v){ if(!can) return; used[v] = 1; set<int> st[3]; for(auto&[to,w] : g[v]){ if(used[to]){ st[w].insert(val[to]); continue; } } if(st[1].size() > 1 || st[2].size() > 1){ can = false; return; } if(!st[1].empty() && !st[2].empty() && *st[2].begin()-*st[1].begin() != K){ can = false; return; } if(st[1].empty() && st[2].empty()){ val[v] = S; } else if(!st[1].empty()){ val[v] = K - *st[1].begin(); } else if(!st[2].empty()){ val[v] = 2*K - *st[2].begin(); } for(auto&[to,w] : g[v]){ if(!used[to]) dfs(to); } return; } void solve(){ int n,m; cin >> n >> m; for(int i = 0; i < m; i++){ int a,b,c; cin >> a >> b >> c; g[a].pb(mp(b,c)); g[b].pb(mp(a,c)); } vector<int> smallestSum; int mn = INF; for(int j = -K; j <= K; j++){ memset(used,0,sizeof used); S = j; can = true; for(int i = 1; i <= n; i++){ for(auto&[to,w] : g[i]){ if(to == i){ val[i] = w*K/2; used[i] = true; } } } for(int i = 1; i <= n; i++){ if(!used[i]) dfs(i); } if(!can) continue; int sum = 0; for(int i = 1; i <= n; i++){ sum += abs(val[i]); } if(sum < mn){ mn = sum; smallestSum.clear(); for(int i = 1; i <= n; i++){ smallestSum.pb(val[i]); } } // cout << "YES\n"; // for(int i = 1; i <= n; i++) // cout << val[i]/2.0 << " "; // return; } if(mn == INF){ cout << "NO\n"; return; } cout << "YES\n"; for(auto& x : smallestSum) cout << x/K << " "; cout << "\n"; return; } signed main(){ ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); // init(); int tests = 1; // cin >> tests; for(int test = 1; test <= tests; test++){ // cerr << "test = " << test << "\n"; solve(); } 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...