oj.uz

Submission #779281

# Submission time Handle Problem Language Result Execution time Memory
779281 2023-07-11T09:49:36 Z mindiyak Traffic (IOI10_traffic) C++14
0 / 100
 1 ms 312 KB 
#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,int>,vector<ll>>> paths;
   vector<bool> processed;
   vector<ll> sum_node;
   ll SUM = 0;

   for(int 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(int 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());

   int ans = 0;
   ll min_distance = SUM;


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

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

      processed[cur_process] = true;
      sum_node[cur_process] = pp[cur_process];
      for(int 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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 0 ms 312 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Incorrect 0 ms 212 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 0 ms 312 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Incorrect 0 ms 212 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 0 ms 312 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Incorrect 0 ms 212 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 0 ms 312 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Incorrect 0 ms 212 KB Output isn't correct
13 Halted 0 ms 0 KB -