Submission #1052095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052095		mychecksedad	Stations (IOI20_stations)	C++17	73.36 / 100	506 ms	1196 KiB

stations

#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second

void dfs(int v, int p, vector<vector<int>> &g, vi &tin, vi &tout, int &timer, vi &dep, vi &labels){
	dep[v] = dep[p] + 1;
	// if(dep[v] % 2) 
		tin[v] = timer++;
	for(int u: g[v]){
		if(u != p) dfs(u, v, g, tin, tout, timer, dep, labels);
	}
	// if(dep[v] % 2 == 0) 
		tout[v] = timer++;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n);
	stack<int> s;
	vector<vector<int>> g(n);
	for(int i = 0; i < n-1; ++i){
		g[u[i]].pb(v[i]);
		g[v[i]].pb(u[i]);
	}

	vector<int> tin(n), tout(n);
	int timer = 0;
	vi dep(n);
	dfs(0, 0, g, tin, tout, timer, dep, labels);

	for(int i = 0; i < n; ++i){
		if(dep[i] % 2) labels[i] = tin[i] * 2;
		else labels[i] = tout[i] * 2 + 1;
	}
	// for(int i = 0; i < n; ++i) cout << tin[i] << ' '; cout << '\n';
	// for(int i = 0; i < n; ++i) cout << tout[i] << ' '; cout << '\n';
	// for(int i = 0; i < n; ++i) cout << labels[i] << ' '; cout << '\n';


	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {

	// cout << s << ' ';
	// for(int u: c) cout << u << ' '; cout << "qu\n";
	if(s % 2 == 0){
		if(t < s || t > c.back()){
			return c.back();
		}
		int val = *lower_bound(all(c), t);
		return val;
	}
	if(t > s || t < c[0]){
		return c[0];
	}
	int val = upper_bound(all(c), t) - c.begin(); --val;
	return c[val];
}

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