Submission #632893

#	Time	Username	Problem	Language	Result	Execution time	Memory
632893		Minindu2006	Traffic (IOI10_traffic)	C++14	100 / 100	2253 ms	170168 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MX = 1e6 + 10;
vector<set<int>> adj(MX);
 
int LocateCentre(int N, int pp[], int S[], int D[])
{
   for (int i = 0; i < N - 1; i++)
   {
      adj[S[i]].insert(D[i]);
      adj[D[i]].insert(S[i]);
   }
   set<pair<int, int>> st;
 
   for (int i = 0; i < N; i++)
      if (adj[i].size() <= 1)
         st.insert({pp[i], i});
   
   while(1)
   {
      if(st.size() == 1)
         break;
      pair<int, int> cur = *st.begin();
      int c = cur.second;
      int p = cur.first;
      st.erase(cur);
 
      auto nxt = *adj[c].begin();
      adj[nxt].erase(c);
      pp[nxt] += p;
      if(adj[nxt].size() == 1)
         st.insert({pp[nxt], nxt});
   }
   return st.begin()->second;
}

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