Submission #1201554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201554		tkm_algorithms	기지국 (IOI20_stations)	C++20	5 / 100	308 ms	500 KiB

stations

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
using ll = long long;

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
//#define int long long

const char nl = '\n';

const int N = 1005;
vector<int> g[N];
int s[N];

void dfs(int a, int p) {
	s[a] = 1;
	for (auto i: g[a]) {
		if (i == p)continue;
		dfs(i, a);
		s[a] += s[i];
	}
}

vector<int> label(int n, int k, vector<int> x, vector<int> v) {
	for (int i = 0; i < n; ++i)g[i].clear();
	
	for (int i = 0; i < n-1; ++i) {
		g[x[i]].push_back(v[i]);
		g[v[i]].push_back(x[i]);
	}
	
	for (int i = 0; i < n; ++i)s[i] = sz(g[i]);
	
	//dfs(0, 0);
	int root = 0;
	for (int i = 0; i < n; ++i)if (s[i] == 1) {
		root = i;
		break;
	}
	
	//cout << root << nl;
	
	int u = root, t = 0, p = root;
	
	vector<int> ans(n);
	ans[root] = t++;
	
	while (true) {
		for (auto i: g[u]) {
			if (i == p)continue;
			p = u; u = i;
			break;
		}
		//cout << u << " ";
		ans[u] = t++;
		if (s[u] == 1 && u != root)break;
	}
	
	return ans;
}

int find_next_station(int ss, int t, vector<int> c) {
	if (ss == t)return ss;
	if (ss < t)return ss+1;
	else return ss-1;
}

//int main() {
	//vector<int> ans;
	//ans = label(6, 100, {5, 0, 4, 2, 1}, {0, 4, 2, 1, 3});
	//for (auto i: ans)cout << i << " ";
//}

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