Submission #884630

# Submission time Handle Problem Language Result Execution time Memory
884630 2023-12-07T19:24:32 Z PM1 Graph (BOI20_graph) C++17
0 / 100
3 ms 4952 KB
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
const int mxn=1e5+5;
int n,m,mark1[mxn],mark2[mxn],cnt=1,fard=0;
int red[mxn],blue[mxn];
double a[mxn],fardm=0,freee;
vector<pair<int,bool> >v[mxn];
void dfs1(int z,int par=0){
	mark1[z]=1;
	for(auto i:v[z]){
		if(!mark1[i.fr]){
			red[i.fr]=red[z]+(i.sc==1);
			blue[i.fr]=blue[z]+(i.sc==0);
			dfs1(i.fr,z);
		}
		else if((red[z]+red[i.fr]+blue[z]+blue[i.fr])%2==0){
			fard=z;
			if(red[z]+red[i.fr]+(i.sc==1))
				fardm=(double)1/2;
			else
				fardm=(double)1;
		}
	}
}
double dfs2(int z,double x){
	a[z]=x;
	mark2[z]=1;
	double res=0;
	for(auto i:v[z]){
		if(!mark2[i.fr]){
			double y=(i.sc)?(double)2-x:(double)1-x;
			res+=dfs2(i.fr,y);
		}
		else {
			double y=(i.sc)?(double)2-x:(double)1-x;
			if(a[i.fr]!=y)
				cnt=0;
		}
	}
	mark2[z]=0;
	return res+abs(x);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,c;
		cin>>x>>y>>c;
		v[x].push_back({y,--c});
		v[y].push_back({x,c});
	}
	for(int i=1;i<=n;i++){
		if(!mark1[i]){
			fard=fardm=0;
			dfs1(i);
			if(fard!=0)
				freee=dfs2(fard,fardm);
			else{
				int l=-1000,r=1000;
				while(r-l>1){
					int mid=(l+r)/2;
					int x=dfs2(i,mid);
					int y=dfs2(i,mid+1);
					if(x>=y)
						l=mid;
					else
						r=mid;
				}
				if(dfs2(i,l)<dfs2(i,r))
					freee=dfs2(i,l);
			}
			if(!cnt){
				cout<<"NO";
				return 0;
			}
		}
	}
	cout<<setprecision(2);
	cout<<"YES"<<endl;
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
}
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB answer = YES
2 Correct 1 ms 4700 KB answer = YES
3 Correct 1 ms 4700 KB answer = YES
4 Correct 1 ms 4696 KB answer = NO
5 Correct 1 ms 4700 KB answer = YES
6 Correct 1 ms 4952 KB answer = YES
7 Incorrect 1 ms 4700 KB jury has the better answer: jans = YES, pans = NO
8 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB answer = YES
2 Correct 1 ms 4700 KB answer = YES
3 Correct 1 ms 4700 KB answer = YES
4 Correct 1 ms 4696 KB answer = NO
5 Correct 1 ms 4700 KB answer = YES
6 Correct 1 ms 4952 KB answer = YES
7 Incorrect 1 ms 4700 KB jury has the better answer: jans = YES, pans = NO
8 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB answer = YES
2 Correct 1 ms 4700 KB answer = YES
3 Correct 1 ms 4700 KB answer = YES
4 Correct 1 ms 4696 KB answer = NO
5 Correct 1 ms 4700 KB answer = YES
6 Correct 1 ms 4952 KB answer = YES
7 Incorrect 1 ms 4700 KB jury has the better answer: jans = YES, pans = NO
8 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB answer = YES
2 Correct 1 ms 4700 KB answer = YES
3 Correct 1 ms 4700 KB answer = YES
4 Correct 1 ms 4696 KB answer = NO
5 Correct 1 ms 4700 KB answer = YES
6 Correct 1 ms 4952 KB answer = YES
7 Incorrect 1 ms 4700 KB jury has the better answer: jans = YES, pans = NO
8 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB answer = YES
2 Correct 1 ms 4700 KB answer = YES
3 Correct 1 ms 4700 KB answer = YES
4 Correct 1 ms 4696 KB answer = NO
5 Correct 1 ms 4700 KB answer = YES
6 Correct 1 ms 4952 KB answer = YES
7 Incorrect 1 ms 4700 KB jury has the better answer: jans = YES, pans = NO
8 Halted 0 ms 0 KB -