Submission #659628

#	Time	Username	Problem	Language	Result	Execution time	Memory
659628		DemonLord154	Traffic (IOI10_traffic)	C++14	100 / 100	1059 ms	170700 KiB

traffic

#include<iostream>
#include<vector>
using namespace std;

typedef long long ll;

void dfs(int node, int parent, vector<vector<int>> & adjList, vector<ll> & subtreePopulation){
  for (int neighbour: adjList[node]){
    if (neighbour == parent)
      continue;
    dfs(neighbour, node, adjList, subtreePopulation);
    subtreePopulation[node] += subtreePopulation[neighbour];
  }
}

int chooseCity(vector<vector<int>> & adjList, vector<ll> & subtreePopulation){

  int N = (int)adjList.size();
  int chosenCity = 0;
  ll chosenCityMaxConjestion = 0;

  for (int rootNeighbour: adjList[0]){
    chosenCityMaxConjestion = max(chosenCityMaxConjestion, subtreePopulation[rootNeighbour]);
  }

  for (int currentCity=1;currentCity<N;currentCity++){
    
    ll currentCityMaxConjestion = subtreePopulation[0] - subtreePopulation[currentCity];

    for (int neighbour: adjList[currentCity]){
      if (subtreePopulation[neighbour]<subtreePopulation[currentCity]){
        currentCityMaxConjestion = max(currentCityMaxConjestion, subtreePopulation[neighbour]);
      }
    }
    if (chosenCityMaxConjestion > currentCityMaxConjestion){
      chosenCityMaxConjestion = currentCityMaxConjestion;
      chosenCity = currentCity;
    }
  }
  return chosenCity;
}

int LocateCentre(int N, int P[], int S[], int D[] ){
  vector<vector<int>> adjList(N);
  vector<ll> subtreePopulation(N);
  for (int i=0;i<N-1;i++){
    adjList[S[i]].emplace_back(D[i]);
    adjList[D[i]].emplace_back(S[i]);
  }
  for (int i=0;i<N;i++){
    subtreePopulation[i] = P[i];
  }
  dfs(0, -1, adjList, subtreePopulation);

  return chooseCity(adjList, subtreePopulation);
}

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