Submission #430491

#	Time	Username	Problem	Language	Result	Execution time	Memory
430491		alishahali1382	Stations (IOI20_stations)	C++14	76 / 100	1267 ms	848 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": "; for (auto dcba:abcd) cerr<<dcba<<", ";cerr<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) ((int)x.size())

const int inf=1000000100; // 1e9
const ll INF=10000000001000000; // 1e16
const int mod=1000000007;
const int MAXN=1010;

int n, m, k, x, y, a, b, t, ans;
int stt[MAXN], fnt[MAXN], h[MAXN], timer;
vi G[MAXN];

void dfs(int node, int par){
	stt[node]=timer++;
	for (int v:G[node]) if (v!=par){
		h[v]=h[node]+1;
		dfs(v, node);
	}
	fnt[node]=timer++;
}

vi label(int _n, int _k, vi U, vi V){
	n=_n;
	k=_k;
	vi out(n);
	for (int i=0; i<n; i++) G[i].clear();
	for (int i=0; i<n-1; i++){
		int u=U[i], v=V[i];
		G[u].pb(v);
		G[v].pb(u);
	}
	timer=0;
	dfs(0, 0);
	for (int i=0; i<n; i++){
		if (h[i]&1) out[i]=fnt[i];
		else out[i]=stt[i];
	}
	vi comp=out;
	sort(all(comp));
	// for (int i=0; i<n; i++) out[i]=lower_bound(all(comp), out[i])-comp.begin();
	return out;
}

int find_next_station(int s, int t, vi adj){
	// cerr<<"\n";
	// debug2(s, t)
	for (int x:adj) if (x==t) return x;
	if (SZ(adj)==1) return adj[0];
	sort(all(adj));
	if (s<adj[0]){
		// stt
		int par=-1;
		if (s){
			par=adj.back();
			adj.pop_back();
		}
		int stt_s=s, fnt_s=adj.back()+1;
		if (t<stt_s || fnt_s<t) return par;
		return *lower_bound(all(adj), t);
	}
	// fnt
	assert(adj.back()<s);
	int par=adj[0];
	reverse(all(adj));
	adj.pop_back();
	
	int stt_s=adj.back()-1, fnt_s=s;
	if (t<stt_s || fnt_s<t) return par;
	while (SZ(adj)>1){
		int v=adj.back();
		adj.pop_back();
		if (adj.back()<t) continue ;
		return v;
	}
	return adj.back();
}

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