답안 #884634

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
884634 2023-12-07T19:30:50 Z PM1 Graph (BOI20_graph) C++17
0 / 100
1 ms 4732 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];
vector<int>now;
void reset(){
	for(auto i:now){
		mark2[i]=0;
	}
}
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;
		}
	}
	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);
			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]<<" ";
	}
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4696 KB answer = YES
2 Correct 1 ms 4732 KB answer = YES
3 Correct 1 ms 4700 KB answer = YES
4 Correct 1 ms 4700 KB answer = NO
5 Correct 1 ms 4700 KB answer = YES
6 Correct 1 ms 4700 KB answer = YES
7 Incorrect 1 ms 4700 KB jury has the better answer: jans = YES, pans = NO
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4696 KB answer = YES
2 Correct 1 ms 4732 KB answer = YES
3 Correct 1 ms 4700 KB answer = YES
4 Correct 1 ms 4700 KB answer = NO
5 Correct 1 ms 4700 KB answer = YES
6 Correct 1 ms 4700 KB answer = YES
7 Incorrect 1 ms 4700 KB jury has the better answer: jans = YES, pans = NO
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4696 KB answer = YES
2 Correct 1 ms 4732 KB answer = YES
3 Correct 1 ms 4700 KB answer = YES
4 Correct 1 ms 4700 KB answer = NO
5 Correct 1 ms 4700 KB answer = YES
6 Correct 1 ms 4700 KB answer = YES
7 Incorrect 1 ms 4700 KB jury has the better answer: jans = YES, pans = NO
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4696 KB answer = YES
2 Correct 1 ms 4732 KB answer = YES
3 Correct 1 ms 4700 KB answer = YES
4 Correct 1 ms 4700 KB answer = NO
5 Correct 1 ms 4700 KB answer = YES
6 Correct 1 ms 4700 KB answer = YES
7 Incorrect 1 ms 4700 KB jury has the better answer: jans = YES, pans = NO
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4696 KB answer = YES
2 Correct 1 ms 4732 KB answer = YES
3 Correct 1 ms 4700 KB answer = YES
4 Correct 1 ms 4700 KB answer = NO
5 Correct 1 ms 4700 KB answer = YES
6 Correct 1 ms 4700 KB answer = YES
7 Incorrect 1 ms 4700 KB jury has the better answer: jans = YES, pans = NO
8 Halted 0 ms 0 KB -