Submission #1049419

#TimeUsernameProblemLanguageResultExecution timeMemory
1049419LudisseyGraph (BOI20_graph)C++17
5 / 100
1 ms348 KiB
#include <bits/stdc++.h> #define int long long #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() using namespace std; vector<vector<int>> neigh1; vector<vector<int>> neigh2; vector<int> sz; vector<int> visited; vector<int> parent; vector<double> eqCOLOR; bool no=false; int getParent(int a){ return (a==parent[a]) ? a : parent[a]=getParent(parent[a]); } bool eq(double a, double b){ if(abs(a-b)>0.0000000001) return false; return true; } void unite(int a, int b){ a=getParent(a); b=getParent(b); if(a==b) return; if(sz[a]<sz[b]) swap(a,b); sz[a]+=sz[b]; parent[b]=a; } vector<set<pair<int,int>>> neigh; void dfs(int x, double c){ eqCOLOR[x]=c; visited[x]=true; for (auto u : neigh[x]) { if(visited[u.first]) continue; double diff=(double)(u.second)-c; if(eq(eqCOLOR[u.first],-1e9)||eq(eqCOLOR[u.first],diff)) dfs(u.first,diff); else { no=true; return; } } } double colorCOUNT(int x){ double sm=abs(eqCOLOR[x])*(double)sz[x]; visited[x]=false; eqCOLOR[x]=-1e9; for (auto u : neigh[x]) { if(!visited[u.first]) continue; sm+=colorCOUNT(u.first); } return sm; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N,M; cin >> N >> M; neigh1.resize(N); sz.resize(N,1); parent.resize(N,1); eqCOLOR.resize(N,-1e9); neigh2.resize(N); vector<pair<pair<int,int>,int>> ed(M); for (int i = 0; i < N; i++) parent[i]=i; for (int i = 0; i < M; i++) { int a,b,c; cin >> a >> b >> c; a--; b--; if(c==1){ neigh1[a].push_back(b); neigh1[b].push_back(a); }else{ neigh2[a].push_back(b); neigh2[b].push_back(a); } ed[i]={{a,b},c}; } for (int i = 0; i < N; i++){ for (int j = 1; j < sz(neigh1[i]); j++) unite(neigh1[i][j-1],neigh1[i][j]); for (int j = 1; j < sz(neigh2[i]); j++) unite(neigh2[i][j-1],neigh2[i][j]); } unordered_map<int,int> mp; for (int i = 0; i < N; i++){ for (int j = 0; j < sz(neigh1[i]); j++) mp[getParent(neigh1[i][j])]=i+1; for (int j = 0; j < sz(neigh2[i]); j++) { if(mp[getParent(neigh2[i][j])]==i+1) { cout << "NO\n"; return 0; } } } for (int i = 0; i < N; i++){ for (int j = 0; j < sz(neigh1[i]); j++) { if(getParent(i)==getParent(neigh1[i][j])) { if(eq(eqCOLOR[getParent(i)],1)){ cout << "NO\n"; return 0; } eqCOLOR[getParent(i)]=0.5; } } for (int j = 0; j < sz(neigh2[i]); j++) { if(getParent(i)==getParent(neigh2[i][j])) { if(eq(eqCOLOR[getParent(i)],0.5)) { cout << "NO\n"; return 0; } eqCOLOR[getParent(i)]=1; } } } neigh.resize(N); for (int i = 0; i < N; i++) { for (int j = 0; j < sz(neigh1[i]); j++) { if(getParent(i)!=getParent(neigh1[i][j])) neigh[getParent(i)].insert({getParent(neigh1[i][j]),1}); } for (int j = 0; j < sz(neigh2[i]); j++) { if(getParent(i)!=getParent(neigh2[i][j])) neigh[getParent(i)].insert({getParent(neigh2[i][j]),2}); } } visited.resize(N,false); for (int i = 0; i < N; i++){ int j=getParent(i); if(!visited[j]&&eqCOLOR[j]>0) dfs(j,eqCOLOR[j]); } for (int i = 0; i < N; i++){ int j=getParent(i); if(!visited[j]){ if(sz(neigh[j])==0) dfs(j,0); // securite else{ double l=-2, r=2; while(r-l>0.00000001){ double d=(r-l)/(double)3; double mid1=l+d; double mid2=r-d; dfs(j,mid1); double c1=colorCOUNT(j); dfs(j,mid2); double c2=colorCOUNT(j); if(c1<c2){ r=mid2; }else{ l=mid1; } } dfs(j,l); } } } for (int i = 0; i < M; i++) { if(!eq(eqCOLOR[getParent(ed[i].first.first)]+eqCOLOR[getParent(ed[i].first.second)],(double)ed[i].second)) no=true; } if(no){ cout << "NO\n"; }else{ cout << "YES\n"; for (int i = 0; i < N; i++) { cout << fixed << setprecision(7) << (double)(eqCOLOR[getParent(i)])<<" "; } } 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...