Submission #1013682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013682		hasan2006	Traffic (IOI10_traffic)	C++17	50 / 100	5052 ms	259920 KiB

traffic

#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 5e5 + 9 , mod = 1e9 + 7;
int a[N] , b[N] , dp[N] , c[N] , d[N]  , p[N];
vector<int>v[N];

void dfs(int n , int par){
    c[n] = a[n];
    p[n] = par;
    for(auto to : v[n]){
        if(to != par){
            dfs(to , n);
            c[n] += c[to];
        }
    }
}

int LocateCentre(int n, int P[], int S[], int D[]) {
  for(int i = 0; i < n; i++) {
    v[i].clear();
    a[i] = P[i];
  }
  for(int i = 0; i < n - 1; i++) {
    v[S[i]].pb(D[i]);
    v[D[i]].pb(S[i]);
  }
  dfs(0, -1);
  int ansv = 2e9 + 5, ansi = 0;
  for(int i = 0; i < n; i++) {
    int mx = 0;
    for(int j : v[i])
      mx = max(mx, p[i] == j ? c[0] - c[i] : c[j]);
    if(mx < ansv)
        ansv = mx, ansi = i;
  }
  return ansi;
}
// Author : حسن

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