Submission #779289

#	Time	Username	Problem	Language	Result	Execution time	Memory
779289		mindiyak	Traffic (IOI10_traffic)	C++14	50 / 100	565 ms	90376 KiB

traffic

#include "traffic.h"
#include <vector>
#include <algorithm>
#include <iostream>
#define pb push_back
#define mp make_pair

#define ll long long


using namespace std;

int LocateCentre(int N, int pp[], int S[], int D[]) {
   vector<pair<pair<ll,ll>,vector<ll>>> paths;
   vector<bool> processed;
   vector<ll> sum_node;
   ll SUM = 0;

   for(ll i=0;i<N;i++){
      vector<ll> a;
      paths.pb(mp(mp(0,i),a));
      SUM += pp[i];
      sum_node.pb(0);
      processed.pb(false);
   }

   //cout<< "cleared" << endl;

   for(ll i=0;i<N-1;i++){
      paths[S[i]].first.first+=1;
      paths[S[i]].second.pb(D[i]);

      paths[D[i]].first.first+=1;
      paths[D[i]].second.pb(S[i]);
   }

   //cout<< "added paths" << endl;

   sort(paths.begin(),paths.end());

   ll ans = 0;
   ll min_distance = SUM;


   for(ll i=0;i<N;i++){
      //cout<< paths[i].first.second << " has " << paths[i].first.first << " connections {";
      for(ll j=0;j<paths[i].first.first;j++){
         //cout<< paths[i].second[j] << ",";
      }//cout<< "}" << endl;
   }

   for(ll i=0;i<N;i++){
      ll maximum_path = 0;
      ll cur_process = paths[i].first.second;
      //cout<< "processing " << cur_process << " node ";

      processed[cur_process] = true;
      sum_node[cur_process] = pp[cur_process];
      for(ll j=0;j<paths[i].first.first;j++){
         //cout<< "Checking connected node -> " << paths[i].second[j] << " " << processed[paths[i].second[j]];
         if(processed[paths[i].second[j]]){
            //cout<< " check with sur max " << sum_node[paths[i].second[j]];
            sum_node[cur_process] += sum_node[paths[i].second[j]];
            maximum_path = max(maximum_path,sum_node[paths[i].second[j]]);
         }//cout<< endl;
      }
      maximum_path = max(maximum_path,SUM-sum_node[cur_process]);

      if(min_distance > maximum_path){
         min_distance = maximum_path;
         ans = cur_process;
      }

      //cout<< maximum_path << " " << min_distance << " " << ans << endl << endl;
   }

   return ans;
}

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