Submission #551258

#	Time	Username	Problem	Language	Result	Execution time	Memory
551258		Pherokung	Traffic (IOI10_traffic)	C++14	50 / 100	350 ms	74820 KiB

traffic

#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;
#define N 1000005
typedef pair<int,int> pa;
int vis[N],chk[N],cnt[N];
vector<int> adj[N];
priority_queue<pa,vector<pa>,greater<pa> > pq;
int LocateCentre(int n, int p[], int S[], int D[]) {
	for(int i=0;i<=n-2;i++) adj[S[i]].push_back(D[i]), adj[D[i]].push_back(S[i]);
	for(int i=0;i<n;i++) if(adj[i].size() == 1) pq.push({p[i],i}), vis[i] = 1, cnt[i] = 1;
	for(int i=1;i<n;i++){
		int d = pq.top().first, u = pq.top().second;
		pq.pop();
		chk[u] = 1;
		for(auto v : adj[u]){
			cnt[v]++;
			if(cnt[v] == adj[v].size() - 1) pq.push({d + p[v],v});
		}
	}
	for(int i=0;i<n;i++) if(!chk[i]) return i;
}

Compilation message (stderr)

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:18:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |    if(cnt[v] == adj[v].size() - 1) pq.push({d + p[v],v});
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~
traffic.cpp:22:1: warning: control reaches end of non-void function [-Wreturn-type]
   22 | }
      | ^

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