Submission #464816

#	Time	Username	Problem	Language	Result	Execution time	Memory
464816		Benmath	Traffic (IOI10_traffic)	C++14	100 / 100	1335 ms	151212 KiB

traffic

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

int LocateCentre(int N, int pp[], int S[], int D[]) {
   int n=N;
   vector<int>adjl[n+1];
   int sum=0;
   int level[n];
   int vis1[n];
   int dp[n];
   for(int i=0;i<(n-1);i++){
      adjl[S[i]].push_back(D[i]); 
      adjl[D[i]].push_back(S[i]);
   }
   for(int i=0;i<n;i++){
      sum=sum+pp[i];
      dp[i]=0;
      level[i]=0;
      vis1[i]=0;
   }
   queue<int>q;
   q.push(0);
   int maxi=0;
   level[0]=0;
   vis1[0]++;
   while(!q.empty()){
      int a=q.front();
      q.pop();
      for(int i=0;i<adjl[a].size();i++){
         if(vis1[adjl[a][i]]==0){
       //     cout<<a<<" "<<adjl[a][i]<<endl;
            vis1[adjl[a][i]]++;
            level[adjl[a][i]]=level[a]+1;
            if(level[adjl[a][i]]>maxi){
               maxi=level[adjl[a][i]];
            
            }
            q.push(adjl[a][i]);
         }
      }
   }

   vector<int>v[n+1];
   for(int i=0;i<n;i++){
      v[level[i]].push_back(i);
   }
   int mini=2000000000;
   int t1=-1;
   for(int i=maxi;i>=0;i--){
      for(int j=0;j<v[i].size();j++){
         int x=v[i][j];
     int maxi1=0;
     
         for(int k=0;k<adjl[x].size();k++){
if(dp[adjl[x][k]]>maxi1){
   maxi1=dp[adjl[x][k]];
}
dp[x]=dp[x]+dp[adjl[x][k]];
         }
         dp[x]=dp[x]+pp[x];
         int sum1=sum-dp[x];
         if(sum1>maxi1){
            maxi1=sum1;
         }
         if(maxi1<mini){
            mini=maxi1;
            t1=x;
         }
      }
   } 
   return t1;
}

Compilation message (stderr)

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |       for(int i=0;i<adjl[a].size();i++){
      |                   ~^~~~~~~~~~~~~~~
traffic.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |       for(int j=0;j<v[i].size();j++){
      |                   ~^~~~~~~~~~~~
traffic.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |          for(int k=0;k<adjl[x].size();k++){
      |                      ~^~~~~~~~~~~~~~~

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