Submission #632876

#	Time	Username	Problem	Language	Result	Execution time	Memory
632876		Minindu2006	Traffic (IOI10_traffic)	C++14	0 / 100	24 ms	47188 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(nxt);
      pp[nxt] += p;
      if(adj[nxt].size() == 1)
         st.insert({pp[nxt], nxt});
   }
   return st.begin()->second;
}

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