Submission #632874

#	Time	Username	Problem	Language	Result	Execution time	Memory
632874		Minindu2006	Traffic (IOI10_traffic)	C++14	0 / 100	28 ms	48076 KiB

traffic

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

const int MX = 1e6 + 10;
vector<int> adj[MX];

int LocateCentre(int N, int pp[], int S[], int D[])
{
   for (int i = 0; i < N - 1; i++)
   {
      adj[S[i]].push_back(D[i]);
      adj[D[i]].push_back(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(st.begin());

      int nxt = *adj[c].begin();
      adj[nxt].erase(adj[c].begin());
      pp[nxt] += c;
      if(adj[nxt].size() == 1)
         st.insert({pp[nxt], nxt});
   }
   return st.begin()->second;
}

Compilation message (stderr)

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:27:11: warning: unused variable 'p' [-Wunused-variable]
   27 |       int p = cur.first;
      |           ^

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