제출 #1018339

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

stations

#include "stations.h"
#include <bits/stdc++.h>
#define rep2(i,a,b) for(int i = (a); i <= (b); i++)
#define pb push_back
using namespace std;

vector<int> graf[1001];
int pre[1001];
int akt_pre = 0;

void dfs(int v, int pop, int dist)
{
	if(dist % 2 == 0) pre[v] = akt_pre;
	akt_pre++;
	for(auto& it: graf[v])
	{
		if(it != pop) dfs(it,v,dist+1);
	}
	if(dist % 2 == 1) pre[v] = akt_pre;
	akt_pre++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) 
{
	rep2(i,0,n-1) graf[i].clear();
	rep2(i,0,n-2)
	{
		graf[u[i]].pb(v[i]);
		graf[v[i]].pb(u[i]);
	}
	akt_pre = 0;
	dfs(0,0,0);
	vector<pair<int,int>> labels;
	rep2(i,0,n-1) labels.pb({pre[i],i});
	sort(labels.begin(),labels.end());
	vector<int> ans(n);
	int akt_poz = 0;
	for(auto& it: labels)
	{
		ans[it.second] = akt_poz;
		akt_poz++;
	}
	return ans;
}

int find_next_station(int s, int t, vector<int> post)
{
	// post
	int n = (int)post.size();
	vector<int> nums = post;
	vector<int> pre(n);
	int root;
	if(s > post[0])
	{
		root = 0;
		swap(pre,post);
		int pop = s;
		for(int i = n-1; i >= 1; i--)
		{
			post[i] = pop-1;
			pop = pre[i];
		}
	}
	else //pre
	{
		root = n-1;
		int pop = s;
		for(int i = 0; i < n-1; i++)
		{
			pre[i] = pop-1;
			pop = post[i];
		}
	}
	for(int i = 0; i < n; i++)
	{
		if(i == root) continue;
		//cout << nums[i] << " " << pre[i] << " " << post[i] << " pre/post\n";
		if(t >= pre[i] && t <= post[i])
 		{
			//cout << nums[i] << " return\n";
			return nums[i];
		}
	}
	//cout << nums[root] << " " << root << " return\n";
	return nums[root];
}

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