Submission #1049460

#TimeUsernameProblemLanguageResultExecution timeMemory
1049460LudisseyGraph (BOI20_graph)C++17
58 / 100
912 ms32868 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<int> eqCOLOR; bool no=false; int getParent(int a){ return (a==parent[a]) ? a : parent[a]=getParent(parent[a]); } 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, int c){ eqCOLOR[x]=c; visited[x]=true; for (auto u : neigh[x]) { if(eqCOLOR[u.first]!=-1&&eqCOLOR[u.first]!=(u.second*2)-c) no=true; if(visited[u.first]) continue; dfs(u.first,(u.second*2)-c); } } int colorCOUNT(int x){ int sm=abs(eqCOLOR[x])*sz[x]; visited[x]=false; eqCOLOR[x]=-1; 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,-1); 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(eqCOLOR[getParent(i)]==2){ cout << "NO\n"; return 0; } eqCOLOR[getParent(i)]=1; } } for (int j = 0; j < sz(neigh2[i]); j++) { if(getParent(i)==getParent(neigh2[i][j])) { if(eqCOLOR[getParent(i)]==1) { cout << "NO\n"; return 0; } eqCOLOR[getParent(i)]=2; } } } 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]); } if(no) { cout << "NO\n"; return 0; } for (int i = 0; i < N; i++){ int j=getParent(i); if(!visited[j]){ if(sz(neigh[j])==0) dfs(j,0); // securite else{ int mn=1e9,mnI=0; for (int k = -70; k <= 70; k++) // sinon binary { dfs(j,k); int c=colorCOUNT(j); if(no) { no=false; continue; } if(c<mn) { mn=c; mnI=k; } } dfs(j,mnI); } } } for (int i = 0; i < M; i++) { if(eqCOLOR[getParent(ed[i].first.first)]+eqCOLOR[getParent(ed[i].first.second)]!=ed[i].second*2) no=true; } if(no){ cout << "NO\n"; }else{ cout << "YES\n"; for (int i = 0; i < N; i++) { cout << (double)(eqCOLOR[getParent(i)])/2<<" "; } } 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...