| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 670448 |
2022-12-09T06:40:55 Z |
jamezzz |
Graph (BOI20_graph) |
C++17 |
|
2 ms |
2668 KB |
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sf scanf
#define pf printf
#define pb push_back
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
#define maxn 100005
int n,m;
double ans[maxn];
ii val[maxn];
vector<int> sub;
vector<ii> AL[maxn];
vector<iii> back;
void dfs(int u,int p){
sub.pb(u);
for(auto[v,w]:AL[u]){
if(v==p)continue;
if(val[v].fi!=0)back.pb({u,v,w});
else{
val[v].fi=-val[u].fi;
val[v].se=w-val[u].se;
dfs(v,u);
}
}
}
int main(){
sf("%d%d",&n,&m);
for(int i=0;i<m;++i){
int a,b,c;sf("%d%d%d",&a,&b,&c);
AL[a].pb({b,c});
AL[b].pb({a,c});
}
for(int i=1;i<=n;++i){
if(val[i].fi!=0)continue;
back.clear();
sub.clear();
val[i]={1,0};
dfs(i,-1);
if(back.size()==0){
vector<double> xs;
for(int i:sub){
xs.pb(-(double)val[i].se/val[i].fi);
}
sort(all(xs));
double x=xs[xs.size()/2];
for(int i:sub){
ans[i]=x*val[i].fi+val[i].se;
}
}
else{
double x=0;
bool done=false,pos=true;
for(auto[a,b,c]:back){
auto[a1,a2]=val[a];
auto[b1,b2]=val[b];
if(done){
if(a1*x+a2+b1*x+b2!=c){
pos=false;
break;
}
}
else{
if(a1+b1==0){
if(a2+b2!=c){
pos=false;
break;
}
}
else{
x=(double)(c-a2-b2)/(a1+b1);
done=true;
}
}
}
if(!pos){
pf("NO\n");
exit(0);
}
for(int i:sub){
ans[i]=val[i].fi*x+val[i].se;
}
}
}
pf("YES\n");
for(int i=1;i<=n;++i){
pf("%f ",ans[i]);
}
}
Compilation message
Graph.cpp: In function 'int main()':
Graph.cpp:36:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | sf("%d%d",&n,&m);
| ^
Graph.cpp:38:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | int a,b,c;sf("%d%d%d",&a,&b,&c);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 3 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2644 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2644 KB |
answer = YES |
| 6 |
Correct |
1 ms |
2668 KB |
answer = YES |
| 7 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 8 |
Incorrect |
1 ms |
2644 KB |
participant answer is larger than the answer of jury |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 3 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2644 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2644 KB |
answer = YES |
| 6 |
Correct |
1 ms |
2668 KB |
answer = YES |
| 7 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 8 |
Incorrect |
1 ms |
2644 KB |
participant answer is larger than the answer of jury |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 3 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2644 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2644 KB |
answer = YES |
| 6 |
Correct |
1 ms |
2668 KB |
answer = YES |
| 7 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 8 |
Incorrect |
1 ms |
2644 KB |
participant answer is larger than the answer of jury |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 3 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2644 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2644 KB |
answer = YES |
| 6 |
Correct |
1 ms |
2668 KB |
answer = YES |
| 7 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 8 |
Incorrect |
1 ms |
2644 KB |
participant answer is larger than the answer of jury |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 3 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2644 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2644 KB |
answer = YES |
| 6 |
Correct |
1 ms |
2668 KB |
answer = YES |
| 7 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 8 |
Incorrect |
1 ms |
2644 KB |
participant answer is larger than the answer of jury |
| 9 |
Halted |
0 ms |
0 KB |
- |
