제출 #1313221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313221		BigBadBully	기지국 (IOI20_stations)	C++20	100 / 100	393 ms	592 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
const int inf = 1e9;


vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	vector<int> bi(n,0);
	vector<int> sbt(n,1),c(n,1);
	vector<vector<int>> graph(n);
	for(int i = 0; i < n-1; i++)
	{
		graph[u[i]].push_back(v[i]);
		graph[v[i]].push_back(u[i]);
	}
	function<void(int,int)> dfs = [&](int cur,int prev)
	{
		c[cur] = 1-c[prev];
		for(int a : graph[cur])
			if(a!=prev)
				dfs(a,cur),sbt[cur]+=sbt[a];
	};
	dfs(0,0);
	int t = 0;
	dfs =[&](int cur,int prev)
	{
		if(c[cur])
			bi[cur]=t+sbt[cur]-1;
		else
			bi[cur]=t++;
		for(int a : graph[cur])
			if(a!=prev)
				dfs(a,cur);
		if(c[cur])t++;
	};
	dfs(0,0);
	return bi;
}

int find_next_station(int s, int t, vector<int> c) {
	if(find(c.begin(),c.end(),t)!=c.end())
		return t;
	if(s==0)
		return *upper_bound(c.begin(),c.end(),t);
	if(s < c[0])
	{
		c.insert(c.begin(),s);
		if(t<c[0])
			return c.back();
		if(t>c.back())
			return c.back();
		int x = *upper_bound(c.begin(),c.end(),t);	
		return x;
	}
	else
	{
		c.push_back(s);
		if(t<c[0])
			return c[0];
		if(t>c.back())
			return c[0];
		int x = *--upper_bound(c.begin(),c.end(),t);
		return x;
	}
	return c[0];
}

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