Submission #1210247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210247		pera	Stations (IOI20_stations)	C++20	10 / 100	307 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};
   };
   int ans;
   auto [ni , nj] = f(s);
   auto [nx , ny] = f(t);
   int parent;
   for(int x : c){
      auto [l , r] = f(x);
      if(l <= ni && nj <= r){
         parent = x;
         break;
      }
   }
   if(ni <= nx && ny <= nj){
      for(auto x : c){
         auto [l , r] = f(x);
         if(l <= nx && ny <= r && x != parent){
            return x;
         }
      }
   }
   return parent;
}

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