Submission #632879

#	Time	Username	Problem	Language	Result	Execution time	Memory
632879		Minindu2006	Traffic (IOI10_traffic)	C++14	0 / 100	57 ms	95636 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]);
   }
   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(1)
   {
      if(st.size() == 1)
         break;
      pair<int, int> cur = st.top();
      int c = cur.second;
      int p = cur.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