제출 #1270727

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270727		WH8	기지국 (IOI20_stations)	C++20	0 / 100	3128 ms	1861440 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
int t=0;
vector<int> disc, v(1005, -1),in(1005, -1), out(1005, -1), dep(1005, 0);
vector<vector<int>> al(1005);
void dfs(int x, int p){
	in[x]=t++;
	for(auto to:al[x]){
		if(to==p)continue;
		dep[to]=dep[x]+1;
		dfs(to,x);
	}
	out[x]=t++;
	if(dep[x]%2==0)v[x]=in[x];
	else v[x]=out[x];
	disc.push_back(v[x]);
	//~ printf("at %lld, in %lld out %lld v[x] %lld\n", x, in[x], out[x], v[x]);
}

vector<int> label(int n, int k,vector<int> a, vector<int> b) {
	for(int i=0;i<n-1;i++){
		al[b[i]].push_back(a[i]);
		al[a[i]].push_back(b[i]);
	}
	dfs(0, -1);
	//~ for(int i=0;i<n;i++){
		//~ cout<<in[i]<<" "<<out[i]<<" : " << v[i]<<endl;
	//~ }
	sort(disc.begin(),disc.end());
	
	for(int i=0;i<n;i++){
		v[i]=lower_bound(disc.begin(),disc.end(),v[i])-disc.begin();
	}
	vector<int> labels(n);
	for (int i = 0; i < n; i++) {
		labels[i] = v[i];
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	int sz=c.size();
	if(sz==1){
		return c[0];
	}
	assert((s <= c[0]) ^ (s >= c[sz-1]));
	if(s<=c[0]){
		for(int i=0;i<sz;i++){
			if(t <= c[i]) return c[i];
		}
		return c[sz-1];
	}
	else {
		for(int i=sz-1;i>=0;i--){
			if(t >= c[i])return c[i];
		}
		return c[0];
	}
}

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