Submission #884630

#	Time	Username	Problem	Language	Result	Execution time	Memory
884630		PM1	Graph (BOI20_graph)	C++17	0 / 100	3 ms	4952 KiB

Graph

#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]<<" ";
	}
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 12
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 42