제출 #796316

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
796316		TimDee	Traffic (IOI10_traffic)	C++17	100 / 100	1191 ms	156760 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back

const int N=1e6;
int sz[N];
int z[N];
vector<int> adj[N];
int a[N];

void dfs2(int u, int p, int out) {
   if (p!=-1) z[p]=max(z[p],sz[u]);
   for(auto&v:adj[u]) {
      if (v==p) continue;
      z[v]=max(z[v],sz[u]-sz[v]+out);
      dfs2(v,u,sz[u]-sz[v]+out);
   }
}
void dfs(int u, int p) {
   sz[u]+=a[u];
   for(auto&v:adj[u]) {
      if (v==p) continue;
      dfs(v,u);
      sz[u]+=sz[v];
   }
}

int LocateCentre(int n, int p[], int s[], int d[]) {
   forn(i,n) a[i]=p[i];
   forn(i,n-1) {
      int u=s[i], v=d[i];
      adj[u].pb(v);
      adj[v].pb(u);
   }
   dfs(0,-1);
   dfs2(0,-1,0);
   int ans=0;
   forn(i,n) if (z[i]<z[ans]) ans=i;
   return ans;
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25