Submission #696355

#	Time	Username	Problem	Language	Result	Execution time	Memory
696355		esomer	Stations (IOI20_stations)	C++17	100 / 100	899 ms	720 KiB

stations

#include<bits/stdc++.h>
 
using namespace std;
 
#define endl "\n"
 
typedef long long int ll;

const int MOD = 1e9 + 7;

vector<int> ans;
int cnt;

void DFS(int x, vector<vector<int>>& adj, int p, int d){
	if(d%2 == 0) {ans[x] = cnt; cnt++;}
	for(int node : adj[x]){
		if(node != p) DFS(node, adj, x, d + 1);
	}
	if(d%2 == 1){ans[x] = cnt; cnt++;}
}

vector<int> label(int n, int k, vector<int> u, vector<int> v){
	vector<vector<int>> adj(n);
	cnt = 0;
	ans.resize(n);
	for(int i = 0; i < n - 1; i++){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	DFS(0, adj, -1, 0);
	return ans;
}

int find_next_station(int s, int t, vector<int> c){
	bool st = 1;
	if(s > c[0]) st = 0;
	int n = (int)c.size();
	int start = s;
	for(int i = 0; i < n; i++){
		if(st == 0 && i == 0) continue;
		else if(st == 1 && i == n - 1) continue;
		if(st == 1){
			if(t > start && t <= c[i]){
				return c[i];
			}else start = c[i];
		}else{
			if(i == n - 1){
				if(t >= c[i] && t < s) return c[i];
			}else{
				if(t >= c[i] && t < c[i + 1]){
					return c[i];
				}
			}
		}
	}
	if(st == 0) return c[0];
	else return c[n - 1];
}

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