제출 #306667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
306667		errorgorn	기지국 (IOI20_stations)	C++17	100 / 100	1166 ms	1536 KiB

stations

#include "stations.h"
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
 
#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
 
 
//idea is label stores in and out time. this is bounded by 1000**2
 
vector<int> al[1005];
int in[1005];
int out[1005];
int d[1005];
 
int TIME;
void dfs(int i,int p){
	in[i]=++TIME;
	
	for (auto &it:al[i]){
		if (it==p) continue;
		
		d[it]=d[i]+1;
		dfs(it,i);
	}
	out[i]=++TIME;
}
 
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	rep(x,0,1005) al[x].clear();
	
	rep(x,0,n-1){
		al[u[x]].push_back(v[x]);
		al[v[x]].push_back(u[x]);
	}
	
	TIME=-1;
	dfs(0,-1);
	
	vector<int> labels;
	rep(x,0,n){
		if (d[x]%2==0) labels.push_back(in[x]);
		else labels.push_back(out[x]);
	}
	
	vector<int> uni;
	rep(x,0,n) uni.push_back(labels[x]);
	
	sort(all(uni));
	map<int,int> id;
	rep(x,0,n) id[uni[x]]=x;
	
	rep(x,0,n) labels[x]=id[labels[x]];
	
	//rep(x,0,n) cout<<labels[x]<<" "; cout<<endl;
	
	return labels;
}
 
int find_next_station(int s, int t, std::vector<int> c) {
	if (s==0){ //this is for root
		for (auto &it:c){
			if (t<=it) return it;
		}
	}
	else if (c.back()<s){ //this is a outdegree thing, c[0] is parent
		c.push_back(s);
		if (sz(c)>1) rep(x,1,sz(c)-1){
			if (c[x]<=t && t<c[x+1]) return c[x];
		}
		return c[0];
	}
	else{
		if (s<t && t<=c[0]) return c[0];
		if (sz(c)>1) rep(x,0,sz(c)-2){
			if (c[x]<t && t<=c[x+1]) return c[x+1];
		}
		return c.back();
	}
	exit(-1);
	return -1;
}

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