Submission #1206812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206812		ansori	Stations (IOI20_stations)	C++17	100 / 100	303 ms	592 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
vector<int> g[N] , lab;
int tim , in[N] , out[N];
void dfs(int v , int pr , int d){
	if(d % 2 == 0) lab[v] = tim ++;
	for(auto to : g[v]){
		if(to != pr){
			dfs(to , v , d + 1);
		}
	}
	if(d % 2 == 1) lab[v] = tim ++;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	lab = vector<int> (n , 0);
	for(int i = 0;i <= n; ++ i) g[i].clear();
	for(int i = 0;i < n - 1; ++ i){
		g[v[i]].push_back(u[i]);
		g[u[i]].push_back(v[i]);
	}
	tim = 0;
	dfs(0 , -1 , 0);
	//for(auto to : lab) cout << to << ' ';
	return lab;
}

int find_next_station(int s, int t, std::vector<int> c) {
	// cout << s << ' ' << t << ' ';
	// for(auto to : c) cout << to << ' ';
	// cout << '\n';
	if(s == t) return s;
	if(c[0] > s){
		for(int i = 0;i < c.size() - 1; ++ i){
			if(t >= s and t <= c[i]) return c[i];
		}
		return c.back();
	}
	c.push_back(s);
	for(int i = c.size() - 1;i >= 2; -- i){
		if(i > 1 and t >= c[i - 1] and t < c[i]) return c[i - 1];
	}
	return c[0];
}

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