이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
#define all(v) v.begin() , v.end()
#define sz(a) ((int)a.size())
const int N = 1e5 + 5;
vector<array<int,2>> v[N];
double ans[N];
bool vis[N],vis2[N];
array<int,2> line[N];
int koy=-1;
double val=-1;
vector<int> node;
void upd(int ind,int a,int b){
if(line[ind][0]==0){
line[ind]={a,b};
return;
}
if(line[ind][0]==a && b!=line[ind][1]){
cout << "NO\n";
exit(0);
}
if(line[ind][0]==a) return;
koy=ind;
val=(b+line[ind][1])/2.0L;
}
void dfs(int c){
vis[c]=1;
node.push_back(c);
for(auto E:v[c]){
int x=E[0],u=E[1];
upd(x,-line[c][0],-line[c][1]+u);
if(vis[x]) continue;
dfs(x);
}
}
void dfs2(int c,double val){
ans[c]=val;
vis[c]=vis2[c]=1;
for(auto E:v[c]){
int x=E[0],u=E[1];
if(vis2[x]) continue;
dfs2(x,u-val);
}
}
void _(){
int n,m;
cin >> n >> m;
for(int i=1;i<=m;i++){
int a,b,c;
cin >> a >> b >> c;
v[a].push_back({b,c});
v[b].push_back({a,c});
}
for(int i=1;i<=n;i++){
if(vis[i]) continue;
koy=-1;
node.clear();
upd(i,1,0);
dfs(i);
if(koy!=-1) dfs2(koy,val);
else{
vector<int> S;
for(int x:node){
if(line[x][0]==1) S.push_back(-line[x][1]);
else S.push_back(line[x][1]);
}
sort(all(S));
dfs2(i,line[i][0]*S[sz(S)/2]+line[i][1]);
}
}
cout << "YES\n";
for(int i=1;i<=n;i++) cout << ans[i] << " \n"[i==n];
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
cout << fixed << setprecision(16);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |