제출 #431838

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
431838		gonengazit	기지국 (IOI20_stations)	C++14	0 / 100	907 ms	656 KiB

stations

#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define x first
#define y second
vector<int> labels;
vector<vector<int>> g;
int tme;
void dfs1(int i,int f=0,int t=0, int s=0){
	int tin=++tme;
	for(auto u:g[i]){
		if(u!=f){
			dfs1(u,i,(t+1)%2,(s+1)%3);
		}
	}
	int tout=tme;
	if(t==0){
		labels[i]=6*tin+3*t+s;
	}
	else{
		labels[i]=6*(tin+tout)+3*t+s;
	}
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	tme=-1;
	labels.assign(n,-1);
	g.assign(n,vector<int>());
	for(int i=0; i<n-1; i++){
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	dfs1(0);
	return labels;
}

ii get(int x){
	return ii(x/3%2,x%3);
}
int find_next_station(int s, int t, std::vector<int> c) {

	ii r=get(s);
	s/=6;
	vector<pair<ii,int>> cld;
	int f=-1;
	if(r.x==0){
		int prev=s;
		for(auto i:c){
			if(get(i).y!=(r.y+1)%3){
				f=i;
				continue;
			}
			int k=i/6;
			cld.emplace_back(ii(prev+1,k-(prev+1)),i);
			prev=k-(prev+1);
		}
	}
	else{
		for(auto i:c){
			if(get(i).y!=(r.y+1)%3){
				f=i;
				continue;
			}
			if(!cld.empty())
				cld.back().x.y=i/6-1;
			cld.emplace_back(ii(i/6,-1),i);
		}
		if(!cld.empty()){
			cld.back().x.y=s-(cld[0].x.x-1);
		}
	}

	ii h=get(t);
	t/=6;

	for(auto i:cld){
		if(h.x==0&&i.x.x<=t&&i.x.y>=t){
			return i.y;
		}
		else if(h.x==1&&2*i.x.x<=t&&2*i.x.y>=t){
			return i.y;
		}
	}
	return f;
}
/*
1
5 100
0 1
1 2
1 3
2 4
1
1 4 2*/

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