Submission #308643

#	Time	Username	Problem	Language	Result	Execution time	Memory
308643		pit4h	Stations (IOI20_stations)	C++14	100 / 100	1016 ms	1280 KiB

stations

#include "stations.h"
#include "bits/stdc++.h"
#define st first
#define nd second
using namespace std;
void dfs(int x, int p, vector<int>& h, vector<vector<int>>& g, vector<int>& path) {
	h[x] = h[p] + 1;
	path.push_back(x);
	for(int i: g[x]) {
		if(i != p) {
			dfs(i, x, h, g, path);
		}
	}
	path.push_back(x);
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n);
	vector<vector<int>> g(n);
	for(int i=0; i<n-1; ++i) {
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	for(int i=0; i<n; ++i) {
		sort(g[i].begin(), g[i].end());
	}
	vector<int> h(n), path;
	dfs(0, 0, h, g, path);
	vector<vector<int>> pos(n);
	for(int i=0; i<(int)path.size(); ++i) {
		pos[path[i]].push_back(i);
	}
	vector<pair<int, int>> val(n);
	for(int i=0; i<n; ++i) {
		val[i].nd = i;
		if(h[i]%2==1) {
			val[i].st = pos[i][1];
		}
		else {
			val[i].st = pos[i][0];	
		}
	}
	sort(val.begin(), val.end());
	for(int i=0; i<n; ++i) {
		labels[val[i].nd] = i;
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	int sz = c.size();
	sort(c.begin(), c.end());
	if(c.size()==1) return c[0];
	for(int i: c) if(t==i) return i;
	if(c.back() > s) { // s is pre
		int prv = s;
		for(int i=0; i<sz-1; ++i) {
			if(t > prv && t < c[i])	{
				return c[i];
			}
			prv = c[i];
		}
		return c.back();
	}
	else { // s is post
		int prv = s;
		for(int i=sz-1; i>=1; --i) {
			if(t < prv && t > c[i]) {
				return c[i];
			}
			prv = c[i];
		}
		return c[0];
	}
}

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