Submission #582905

#	Time	Username	Problem	Language	Result	Execution time	Memory
582905		sff_user	Traffic (IOI10_traffic)	C++17	0 / 100	1 ms	340 KiB

traffic

#include <bits/stdc++.h>
#include "traffic.h"

#define pb push_back
#define vi vector<int>

using namespace std;

vector<vi > adj;
int sub[1000006];
int par[1000006];
void dfs(int u , int p, int pp[]){
   sub[u] = pp[u];
   par[u] = p;
   for(int v : adj[u]){
      if(v== p) continue;
      dfs(v,u,pp);
      sub[u] += sub[v];
   }
}

int LocateCentre(int n, int pp[] , int S[], int D[]) {
   adj.resize(n+1);
   for(int i = 0 ; i < n-1 ; i++){
      adj[S[i]].pb(D[i]);
      adj[D[i]].pb(S[i]);
   }   
   dfs(0,-1,pp);
   int a =1e9, b = 0;
   for(int i = 0 ; i < n ; i++){
      for(int j : adj[i]){
         if(j != par[i]){
            b = max(b,sub[j]);
            continue;
         }
         b = max(b,sub[0]-sub[i]);
      }
      a = min(a,b);
   }

   return a;
}

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