# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
779761 |
2023-07-11T18:53:56 Z |
FEDIKUS |
Graph (BOI20_graph) |
C++17 |
|
1 ms |
2644 KB |
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxn=1e5+10;
vector<pair<ll,ll> > g[maxn];
bool moze=true;
bool vis[maxn];
ll val[maxn];
ll sgn[maxn];
ll res[maxn];
bool pola[maxn];
vector<int> comp;
set<ll> a;
void dfs(ll node){
comp.push_back(node);
vis[node]=true;
for(auto i:g[node]){
if(vis[i.first]){
if(sgn[i.first]!=sgn[node] && val[i.first]+val[node]!=i.second) moze=false;
if(sgn[i.first]==sgn[node]){
if(sgn[i.first]==1) a.emplace(i.second-val[node]-val[i.first]);
else a.emplace(val[i.first]+val[node]-i.second);
}
}else{
sgn[i.first]=-sgn[node];
val[i.first]=i.second-val[node];
dfs(i.first);
}
}
}
int main(){
ll n,m;
cin>>n>>m;
for(ll i=0;i<m;i++){
ll u,v,c;
cin>>u>>v>>c;
g[u].push_back({v,c});
g[v].push_back({u,c});
}
for(int i=1;i<=n;i++){
if(vis[i]) continue;
sgn[i]=1;
val[i]=0;
comp.clear();
a.clear();
dfs(i);
if(a.size()>1) moze=false;
if(a.size()==1){
int aa=*a.begin();
for(ll i:comp){
res[i]=aa*sgn[i]/2+val[i];
if(aa&1){
if(sgn[i]<0) res[i]--;
pola[i]=true;
}
}
}
ll best=0;
ll curr=LLONG_MAX;
for(ll i:comp){
ll sum=0;
for(ll j:comp){
sum+=abs(val[j]+val[i]*sgn[j]);
}
if(sum<curr){
curr=sum;
best=val[i];
}
}
for(ll i:comp){
ll sum=0;
for(ll j:comp){
sum+=abs(val[j]-val[i]*sgn[j]);
}
if(sum<curr){
curr=sum;
best=-val[i];
}
}
for(ll i:comp){
res[i]=val[i]+best*sgn[i];
}
}
if(moze){
cout<<"YES\n";
for(int i=1;i<=n;i++) cout<<res[i]<<" ";
}else cout<<"NO\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2644 KB |
Sum of endpoints for edge (1; 3) differs from the expected value 2. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2644 KB |
Sum of endpoints for edge (1; 3) differs from the expected value 2. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2644 KB |
Sum of endpoints for edge (1; 3) differs from the expected value 2. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2644 KB |
Sum of endpoints for edge (1; 3) differs from the expected value 2. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2644 KB |
Sum of endpoints for edge (1; 3) differs from the expected value 2. |
2 |
Halted |
0 ms |
0 KB |
- |