Submission #1270731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270731		WH8	기지국 (IOI20_stations)	C++20	100 / 100	305 ms	648 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> label(int n, int k,vector<int> a, vector<int> b) {
	int t=0;
	
	vector<int> disc, v(n, -1),in(n, -1), out(n, -1), dep(n, 0);
	vector<vector<int>> al(n);
	auto dfs = [&](auto dfs, int x, int p)->void{
		in[x]=t++;
		for(auto to:al[x]){
			if(to==p)continue;
			dep[to]=dep[x]+1;
			dfs(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]);
	};

	for(int i=0;i<n-1;i++){
		al[b[i]].push_back(a[i]);
		al[a[i]].push_back(b[i]);
	}
	dfs(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];
		//~ printf("index %d has label %d\n", i, labels[i]);
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	int sz=c.size();
	assert((s <= c[0]) ^ (s >= c[sz-1]));

	int ret=-1;
	if(sz==1){
		ret=c[0];
	}
	else if(s<=c[0]){
		for(int i=0;i<sz;i++){
			if(t>=s and t <= c[i]){
				ret=c[i];
				break;
			}
			ret=c[i];
		}
	}
	else {
		for(int i=sz-1;i>=0;i--){
			if(t <= s and t >= c[i]){
				ret=c[i];
				break;
			}
			ret=c[i];
		}
	}
	//~ printf("query %d to %d, returning %d\n", s,t,ret);
	return ret;
}

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