제출 #317505

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
317505		rqi	Stations (IOI20_stations)	C++14	0 / 100	2690 ms	2097156 KiB

stations

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

typedef vector<int> vi;
typedef pair<int, int> pi;

#define pb push_back
#define bk back()
#define mp make_pair
#define f first
#define s second
#define all(x) begin(x), end(x)

const int mx = 1005;
vi adj[mx];
int depth[mx];
pi rang[mx];
int cnt = 0;

vi labels;

void genET(int node, int prv = -1, int d = 0){
	depth[node] = d;
	cnt++;
	rang[node].f = rang[node].s = cnt;
	for(auto u: adj[node]){
		if(u == prv) continue;
		genET(u, node, d+1);
		cnt++; 
		rang[node].s = cnt;
	}
	if(depth[node] % 2 == 0){
		labels[node] = rang[node].f;
	}
	else labels[node] = rang[node].s;
}

vi label(int n, int k, vi u, vi v) {
	for(int i = 0; i < n-1; i++){
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
	}
	labels = vi(n);

	genET(0);

	map<int, int> m;
	for(auto u: labels) m[u];
	cnt = 0;
	for(auto &u: m){
		u.s = cnt++;
	} 
	for(auto &u: labels) u = m[u];
	return labels;
}

int find_next_station(int s, int t, vi c) {
	bool typ = 0;
	if(c[0] < s) typ = 1;

	
	if(typ == 0){
		sort(all(c));
		if(t < s) return c.bk;
		for(auto u: c) if(u >= t) return u;
	}
	else{
		sort(c.rbegin(), c.rend());
		if(t > s) return c.bk;
		for(auto u: c) if(u <= t) return u;
	}
	assert(0 == 1);
	return -1;
}

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