Submission #1210238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210238		pera	Stations (IOI20_stations)	C++20	10 / 100	313 ms	592 KiB

stations

#include <bits/stdc++.h>
#include "stations.h"

using namespace std;

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n);
	vector<vector<int>> g(n);
   for(int i = 0;i < n - 1;i ++){
      g[u[i]].emplace_back(v[i]);
      g[v[i]].emplace_back(u[i]);
   }
   int timer = 0;
   vector<int> in(n) , out(n);
   function<void(int , int)> dfs = [&](int u , int p){
      in[u] = ++timer;
      for(int v : g[u]){
         if(v != p){
            dfs(v , u);
         }
      }
      out[u] = timer;
   };
   dfs(0 , 0);
   for(int i = 0;i < n;i ++){
      labels[i] = 1000 * in[i] + out[i];
   }
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
   auto f = [&](int l){
      return pair<int , int>{l / 1000 , l % 1000};
   };
   auto [L , R] = f(t);
   int bst = -1 , len = 1E9 , B , B_len = -1;
   for(int x : c){
      auto [l , r] = f(x);
      if(l <= L && R <= r && len > r - l){
         bst = x;
         len = r - l;
      }  
      if(r - l > B_len){
         B = x;
         B_len = r - l;
      }
   }
   if(bst != -1){
      return bst;
   }
   return B;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 10 / 10
• Subtask 5: 0 / 61