Submission #1240342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240342		AMnu	Stations (IOI20_stations)	C++20	100 / 100	308 ms	576 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e3+5;

int sub[MAXN];
vector <int> ans;
vector <int> adj[MAXN];

void fil(int cur,int par,int L,int R,bool B) {
	if (B) {
		ans[cur] = L;
		for (int nxt : adj[cur]) {
			if (nxt == par) continue;
			fil(nxt,cur,R-sub[nxt]+1,R,!B);
			R -= sub[nxt];
		}
	}
	else {
		ans[cur] = R;
		for (int nxt : adj[cur]) {
			if (nxt == par) continue;
			fil(nxt,cur,L,L+sub[nxt]-1,!B);
			L += sub[nxt];
		}
	}
}

void calc(int cur,int par) {
	sub[cur] = 1;
	for (int nxt : adj[cur]) {
		if (nxt == par) continue;
		calc(nxt,cur);
		sub[cur] += sub[nxt];
	}
}

vector<int> label(int N,int K,vector<int> u,vector<int> v) {
	for (int i=0;i<N;i++) {
		adj[i].clear();
	}
	ans = vector<int>(N);
	for (int i=0;i<N-1;i++) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	calc(0,0);
	fil(0,0,0,N-1,0);
	return ans;
}

int find_next_station(int s,int t,vector<int> c) {
	if (s > c[0]) {
		reverse(c.begin(),c.end());
		for (int x : c) {
			if (t < s && t >= x) {
				return x;
			}
		}
	}
	else {
		for (int x : c) {
			if (t > s && t <= x) {
				return x;
			}
		}
	}
	return c.back();
}

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