Submission #424059

#	Time	Username	Problem	Language	Result	Execution time	Memory
424059		chirathnirodha	Traffic (IOI10_traffic)	C++17	100 / 100	1262 ms	158924 KiB

traffic

#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
ll subtree[1000000];
int parent[1000000];
vector<int> adj[1000000];
ll dfs(int x){
   for(int i=0;i<adj[x].size();i++){
      if(adj[x][i]==0 || parent[adj[x][i]]!=adj[x][i])continue;
      parent[adj[x][i]]=x;
      subtree[x]+=dfs(adj[x][i]);
   }
   return subtree[x];
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
   n=N;
   ll total=0;
   for(int i=0;i<n;i++){
      subtree[i]=(long long) pp[i];
      parent[i]=i;
      total+=subtree[i];
   }
   for(int i=0;i<n-1;i++){adj[S[i]].push_back(D[i]);adj[D[i]].push_back(S[i]);}
   dfs(0);
   int child[n];child[0]=adj[0].size();
   queue<int> q;
   for(int i=1;i<n;i++){
      child[i]=adj[i].size()-1;
      if(child[i]==0)q.push(i);
   }
   ll cost[n];memset(cost,0,sizeof(cost));
   while(!q.empty()){
      int c=q.front();q.pop();
      if(parent[c]==c)continue;
      cost[c]=max(cost[c],total-subtree[c]);
      cost[parent[c]]=max(cost[parent[c]],subtree[c]);
      child[parent[c]]--;
      if(parent[parent[c]]!=parent[c] && child[parent[c]]==0)q.push(parent[c]);
   }
   pair<ll,int> ans;ans.first=cost[0];ans.second=0;
   for(int i=0;i<n;i++){
      if(ans.first>cost[i]){
         ans.first=cost[i];
         ans.second=i;
      }
   }
   return ans.second;
}

Compilation message (stderr)

traffic.cpp: In function 'll dfs(int)':
traffic.cpp:11:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |    for(int i=0;i<adj[x].size();i++){
      |                ~^~~~~~~~~~~~~~

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