Submission #542063

#	Time	Username	Problem	Language	Result	Execution time	Memory
542063		Mdominykas	Traffic (IOI10_traffic)	C++14	100 / 100	1381 ms	156000 KiB

traffic

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

using namespace std;

int LocateCentre(int N, int pp[], int S[], int D[]) {
   // cout << "pradzia - kita" << endl;
   // cout << "imsiu vektoriu" << endl;
   vector<int> adj[N];
   // cout << "vektoriu gavau " << endl;
   for(int i = 0; i < N; i++)
   {
      // assert(S[i] < N);
      // assert(D[i] < N);
      adj[S[i]].push_back(D[i]);
      adj[D[i]].push_back(S[i]);
   }

   // cout << "ne assertionai" << endl;

   int totPeople = 0;
   for(int i = 0; i < N; i++)
      totPeople += pp[i];

   vector<int> children[N];
   int parent[N];
   bool visited[N];
   for(int i = 0; i < N; i++)
   {
      parent[i] = -1;
      visited[i] = 0;
   }

   // cout << "pries ciklis" << endl;

   int root = 0;
   queue<int> q;
   q.push(root);
   parent[root] = -1;
   vector<int> order;
   while(!q.empty())
   {
      int g = q.front();
      q.pop();
      if(visited[g])
         continue;
      order.push_back(g);
      visited[g] = true;

      for(int next : adj[g])
      {
         if(!visited[next])
         {
            children[g].push_back(next);
            q.push(next);
            parent[next] = g;
         }
      }
   }

   // cout << "po ciklis " << endl;

   reverse(order.begin(), order.end());

   int subtreeSize[N];
   int maxCon[N];
   for(int i = 0; i < N; i++)
   {
      subtreeSize[i] = 0;
      maxCon[i] = 0;
   }

   for(int v : order)
   {
      subtreeSize[v] = pp[v];
      for(int child : children[v])
      {
         maxCon[v] = max(maxCon[v], subtreeSize[child]);
         subtreeSize[v] += subtreeSize[child];
      }
      maxCon[v] = max(maxCon[v], totPeople - subtreeSize[v]);
   }


   int mini = 0;
   for(int i = 0; i < N; i++)
   {
      if(maxCon[i] < maxCon[mini])
         mini = i;
   }
   return mini;
}

Compilation message (stderr)

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:26:8: warning: variable 'parent' set but not used [-Wunused-but-set-variable]
   26 |    int parent[N];
      |        ^~~~~~

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