Submission #632887

#	Time	Username	Problem	Language	Result	Execution time	Memory
632887		Minindu2006	Traffic (IOI10_traffic)	C++14	0 / 100	1 ms	468 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;



int LocateCentre(int N, int pp[], int S[], int D[])
{
   vector<set<int>> adj(N + 1);
   for (int i = 0; i < N - 1; i++)
   {
      adj[S[i]].insert(D[i]);
      adj[D[i]].insert(S[i]);
   }
   priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> st;
   for (int i = 0; i < N; i++)
      if (adj[i].size() == 1)
         st.push({pp[i], i});
   
   while(st.size() >= 2)
   {
      int c = st.top().second;
      int p = st.top().first;
      st.pop();

      auto nxt = *adj[c].begin();
      adj[nxt].erase(c);
      pp[nxt] += p;
      if(adj[nxt].size() == 1)
         st.push({pp[nxt], nxt});
   }
   return st.top().second;
}

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