Submission #1188187

#TimeUsernameProblemLanguageResultExecution timeMemory
1188187mertbbmGraph (BOI20_graph)C++20
0 / 100
1 ms2624 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ld long double #define show(x,y) cout << y << " " << #x << endl; #define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl; #define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl; #define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl; typedef pair<int,int>pii; typedef pair<int,pii>pi2; mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count()); vector<pii>adj[100005]; bool visited[100005]; vector<int>storage[2]; pii arr[100005]; bool amos=true; vector<int>need; void dfs(int index, int val, int sgn){ arr[index]={val,sgn}; storage[sgn].push_back(val); //show3(index,index,val,val,sgn,sgn); visited[index]=true; for(auto it:adj[index]){ int nval=it.second-val; int nsgn=1-sgn; if(visited[it.first]){ if(arr[it.first].second==nsgn&&arr[it.first].first!=nval) amos=false; if(arr[it.first].second!=nsgn){ int a=arr[it.first].first; int b=nval; if(nsgn) swap(a,b); //b is the k-x need.push_back(b-a); } } if(!visited[it.first]){ dfs(it.first,nval,nsgn); } } } void solve(){ int n,m; cin >> n >> m; int temp,temp2,temp3; for(int x=0;x<m;x++){ cin >> temp >> temp2 >> temp3; adj[temp].push_back({temp2,temp3}); adj[temp2].push_back({temp,temp3}); } dfs(1,0,1); //show(amos,amos); int counter=0; while(!storage[0].empty()&&!storage[1].empty()){ counter+=storage[0].back(); counter+=storage[1].back(); storage[0].pop_back(); storage[1].pop_back(); } ld hold=0; if(!storage[0].empty()){ //k-x sort(storage[0].begin(),storage[0].end()); hold=storage[0][storage[0].size()/2]; } if(!storage[1].empty()){ //k+x sort(storage[1].begin(),storage[1].end()); hold=-storage[1][storage[1].size()/2]; } //show4(need,need); //sort(need.begin(),need.end()); need.resize(unique(need.begin(),need.end())-need.begin()); if(!amos||need.size()>1){ cout << "NO\n"; } else{ if(!need.empty()) hold=(ld)need[0]/2; cout << "YES\n"; for(int x=1;x<=n;x++){ ld cur=arr[x].first; if(arr[x].second==1) cur-=hold; else cur+=hold; cout << fixed << setprecision(10) << cur << " "; } } } int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int t=1; //cin >> t; while(t--){ solve(); } }
#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...