Submission #1101975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101975		epicci23	Graph (BOI20_graph)	C++17	100 / 100	140 ms	26056 KiB

Graph

#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]){
      if(u-val!=ans[x]){
        cout << "NO\n";
        exit(0);
      }
      continue;
    }
    else 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;
}

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 42 / 42