Submission #1180249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180249		Pacybwoah	Stations (IOI20_stations)	C++20	52.32 / 100	317 ms	600 KiB

stations

#include "stations.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
namespace{
	vector<vector<int>> graph;
	vector<int> sz, in;
	int cnt = 0;
	const int inf = 1e9;
	void dfs(int node, int parent){
		sz[node] = 1;
		int mini = inf, best = -1;
		for(auto &x: graph[node]){
			if(x == parent) continue;
			dfs(x, node);
			sz[node] += sz[x];
			if(sz[x] < mini){
				mini = sz[x];
				best = x;
			}
		}
		if(best != -1){
			for(auto &x: graph[node]){
				if(best == x){
					swap(x, graph[node][(int)graph[node].size() - 1]);
					break;
				}
			}
		}
	}
	void dfs2(int node, int parent){
		in[node] = cnt;
		cnt++;
		for(auto &x: graph[node]){
			if(x == parent) continue;
			dfs2(x, node);
		}
	}
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v){
	vector<int>().swap(sz);
	vector<int>().swap(in);
	vector<vector<int>>().swap(graph);
	sz.resize(n);
	in.resize(n);
	graph.resize(n);
	cnt = 0;
	for(int i = 0; i < n - 1; i++){
		graph[u[i]].push_back(v[i]);
		graph[v[i]].push_back(u[i]);
	}
	dfs(0, 0);
	dfs2(0, 0);
	vector<int> ret(n);
	for(int i = 0; i < n; i++){
		ret[i] = sz[i] * 1000 + in[i];
	}
	return ret;
}

int find_next_station(int s, int t, std::vector<int> c){
	int lab = t % 1000;
	int up = 0;
	for(auto &x: c){
		int sz = x / 1000, in = x % 1000;
		if(in < s % 1000){
			up = x;
			continue;
		}
		int out = in + sz - 1;
		if(in <= lab && lab <= out) return x;
	}
	return up;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run -g stations.cpp stub.cpp

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