Submission #730750

#	Time	Username	Problem	Language	Result	Execution time	Memory
730750		sentheta	Stations (IOI20_stations)	C++17	100 / 100	930 ms	1196 KiB

stations

#include "stations.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

const int N = 1005;

V<int> adj[N];

int d[N];
int in[N], out[N];
int t = 0;
void dfs(int x=0,int par=-1){
	in[x] = t++;
	for(int y : adj[x]) if(y!=par){
		d[y] = d[x]+1;
		dfs(y, x);
	}
	out[x] = t++;
}

V<int> label(int n,int k,V<int> u,V<int> v){
	rep(i,0,n){
		adj[i].clear();
	}
	rep(i,0,n-1){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}

	t = 0;
	dfs();

	map<int,int> zip;
	rep(i,0,n){
		if(d[i]%2==0) zip[in[i]];
		else zip[out[i]];
	}
	t = 0;
	for(auto&[p,q] : zip) q = t++;

	V<int> ans;
	rep(i,0,n){
		if(d[i]%2==0) ans.push_back(zip[in[i]]);
		else ans.push_back(zip[out[i]]);
	}

	return ans;
}

int find_next_station(int s,int t,V<int> c){
	// s is in[x]
	if(s < c[0]){
		int par = s==0 ? -1 : c.back();

		int l = s+1;
		for(int r : c) if(r!=par){
			if(l<=t && t<=r) return r;
			l = r+1;
		}
		return par;
	}
	// s is out[x]
	else{
		int par = c[0];

		c.push_back(s);
		rep(i,0,c.size()-1){
			if(c[i]<=t && t<=c[i+1]-1) return c[i];
		}
		return par;
	}
}

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