제출 #622880

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
622880		yanndev	기지국 (IOI20_stations)	C++17	76 / 100	935 ms	804 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int MX = 1042;

int in[MX];
int out[MX];
int dep[MX];
int dfsT = 0;
vector<int> adj[MX];

void dfs(int node, int par, int d) {
	//cout << "cur " << node << '\n';
	dep[node] = d;
	in[node] = dfsT++;
	for (auto& x: adj[node])
		if (x != par)
			dfs(x, node, d + 1);
	out[node] = dfsT++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	//cout << "called\n";
	dfsT = 0;
	vector<int> labels(n);

	for (int i = 0; i < n; i++)
		adj[i].clear();

	for (int i = 0; i + 1 < n; i++) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}

	dfs(0, -1, 0);

	for (int i = 0; i < n; i++)
		labels[i] = ((dep[i] % 2) == 0) ? in[i] : out[i];
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	c.push_back(s);
	sort(c.begin(), c.end());

	if (c[0] == s) {
		// s is tin
		// the rest is tout
		int par = c.back(); // par has max tout
		int curIn = c[0] + 1;

		for (int i = 1; i + 1 < (int)c.size(); i++) {
			int inTime = curIn;
			int outTime = c[i];
			if (inTime <= t && t <= outTime)
				return c[i];
			curIn = outTime + 1;
		}

		return par;
	} else {
		// s is tout
		// the rest is tin
		int par = c[0];
		int curOut = c.back() - 1;
		for (int i = (int)c.size() - 1; i > 0; i--) {
			int inTime = c[i];
			int outTime = curOut;
			if (inTime <= t && t <= outTime)
				return c[i];
			curOut = inTime - 1;
		}

		return par;
	}
}

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