Submission #884638

#	Time	Username	Problem	Language	Result	Execution time	Memory
884638		PM1	Graph (BOI20_graph)	C++17	0 / 100	1 ms	4856 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,dis[mxn];
double a[mxn],fardm=0,freee,b[mxn];
vector<pair<int,bool> >v[mxn];
vector<int>now;
void reset(){
	for(auto i:now){
		mark2[i]=0;
	}
}
void dfs1(int z,double x=0,int d=0,int par=0){
	mark1[z]=1;
	b[z]=x;
	dis[z]=d%2;
	for(auto i:v[z]){
		if(!mark1[i.fr]){
			double y=(i.sc)?(double)2-x:(double)1-x;
			dfs1(i.fr,y,d+1,z);
		}
		else if(dis[i.fr]==dis[z] && i.fr!=par){
			fard=z;
			int y=i.sc+1;
			fardm=(double)(y-b[z]-b[i.fr])/2;
		}
	}
	now.push_back(z);
}
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;
		}
	}
	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);
			//cout<<fard<<" "<<fardm<<endl;
			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);
					reset();
					int y=dfs2(i,mid+1);
					reset();
					if(x>=y)
						l=mid;
					else
						r=mid;
				}
				int x=dfs2(i,l);
				reset();
				int y=dfs2(i,r);
				reset();
				if(x<y)
					freee=dfs2(i,l);
			}
			if(!cnt){
				cout<<"NO";
				return 0;
			}
			now.clear();
		}
	}
	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