Submission #241615

#	Time	Username	Problem	Language	Result	Execution time	Memory
241615		lakshith_	Traffic (IOI10_traffic)	C++14	50 / 100	5066 ms	29176 KiB

traffic

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

using namespace std;

vector<vector<int>> adjList(1000000,vector<int>());

int DFS(int n,int s,int* p){
  int sum = p[n];
  for(int x:adjList.at(n))
    if(x!=s)sum += DFS(x,n,p);
  return sum;
}

int LocateCentre(int n,int p[],int s[],int d[]){
  for(int i=0;i<n-1;i++){
    adjList.at(s[i]).pb(d[i]);
    adjList.at(d[i]).pb(s[i]);
  }
  int MIN = INT_MAX;
  int minPos = 0;
  for(int i=0;i<n;i++){
    int MAX = 0;
    for(int x:adjList.at(i))
      MAX = max(MAX,DFS(x,i,p));
    if(MAX < MIN){
      MIN = MAX;
      minPos = i;
    }
  }
  return minPos;
}

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