제출 #672994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
672994		vjudge1	기지국 (IOI20_stations)	C++17	0 / 100	848 ms	664 KiB

stations

#include <vector>
#include <algorithm>
//#include "IOI20_Stations.h"
//const int N = 1e5;
int cnt=0;

std::vector<int> labels;

/*
clarifications:
k == n-1
c is sorted


Debugging:
- Idea => Proof
- Code => Accepted

*/

std::vector<std::vector<int>> g;
void dfs(int node, int par) {
	for (int ch : g[node]) {
		if (ch != par) {
			dfs(ch, node);
		}
	}
	labels[node] = cnt++;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	/*
	1. Construct adjacency list
	2. Label every node with its entrence time (dt)
	*/
	g.clear();
	g.resize(n);
	cnt = 1;
	for (int i = 0; i < n - 1;i++) {
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	//cnt = 0;
	labels.clear();
	labels.resize(n);
	dfs(0, -1);
	return labels;
}

/*
1. Now it's easy to find where to countinue the path
2. Tha path will be behined (i.e. the parent of current node), if the distinatin was less than it
3. The path will be greater than or equal to any of the nighbours
4. If the distination was greater than or equals the node i, and less than any nighbour greater than i, then we need to go there
*/
int find_next_station(int s, int t, std::vector<int> c) {
	int sz = c.size();
	if (t < s) return c[sz-1];
	for (int i = 0; i < sz-1; i++) {
		if (t <= c[i]) return c[i];
	}
	return c[sz - 2];
}

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