| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 884638 |
2023-12-07T19:57:25 Z |
PM1 |
Graph (BOI20_graph) |
C++17 |
|
1 ms |
4856 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,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]<<" ";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4696 KB |
answer = YES |
| 2 |
Correct |
1 ms |
4856 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 |
Correct |
1 ms |
4720 KB |
answer = YES |
| 8 |
Correct |
1 ms |
4696 KB |
answer = YES |
| 9 |
Correct |
1 ms |
4700 KB |
answer = NO |
| 10 |
Correct |
1 ms |
4724 KB |
answer = YES |
| 11 |
Incorrect |
1 ms |
4696 KB |
jury has the better answer: jans = YES, pans = NO |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4696 KB |
answer = YES |
| 2 |
Correct |
1 ms |
4856 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 |
Correct |
1 ms |
4720 KB |
answer = YES |
| 8 |
Correct |
1 ms |
4696 KB |
answer = YES |
| 9 |
Correct |
1 ms |
4700 KB |
answer = NO |
| 10 |
Correct |
1 ms |
4724 KB |
answer = YES |
| 11 |
Incorrect |
1 ms |
4696 KB |
jury has the better answer: jans = YES, pans = NO |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4696 KB |
answer = YES |
| 2 |
Correct |
1 ms |
4856 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 |
Correct |
1 ms |
4720 KB |
answer = YES |
| 8 |
Correct |
1 ms |
4696 KB |
answer = YES |
| 9 |
Correct |
1 ms |
4700 KB |
answer = NO |
| 10 |
Correct |
1 ms |
4724 KB |
answer = YES |
| 11 |
Incorrect |
1 ms |
4696 KB |
jury has the better answer: jans = YES, pans = NO |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4696 KB |
answer = YES |
| 2 |
Correct |
1 ms |
4856 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 |
Correct |
1 ms |
4720 KB |
answer = YES |
| 8 |
Correct |
1 ms |
4696 KB |
answer = YES |
| 9 |
Correct |
1 ms |
4700 KB |
answer = NO |
| 10 |
Correct |
1 ms |
4724 KB |
answer = YES |
| 11 |
Incorrect |
1 ms |
4696 KB |
jury has the better answer: jans = YES, pans = NO |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4696 KB |
answer = YES |
| 2 |
Correct |
1 ms |
4856 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 |
Correct |
1 ms |
4720 KB |
answer = YES |
| 8 |
Correct |
1 ms |
4696 KB |
answer = YES |
| 9 |
Correct |
1 ms |
4700 KB |
answer = NO |
| 10 |
Correct |
1 ms |
4724 KB |
answer = YES |
| 11 |
Incorrect |
1 ms |
4696 KB |
jury has the better answer: jans = YES, pans = NO |
| 12 |
Halted |
0 ms |
0 KB |
- |
