Submission #1067357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067357		Lalic	Stations (IOI20_stations)	C++17	0 / 100	584 ms	1020 KiB

stations

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

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(). x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;

const int INF = 0x3f3f3f3f;

void build(int ver, int prev, vector<int>& labels, bool isMax, int& cnt, vector<vector<int>>& adj, vector<int>& submin, vector<int>& submax){
	if(prev!=-1 && (int)adj[ver].size()==1){
		labels[ver]=cnt;
		submin[ver]=submax[ver]=cnt;
		cnt++;
		return;
	}
	
	int mx=-INF, mn=INF;
	for(auto u : adj[ver]){
		if(u==prev) continue;
		build(u, ver, labels, !isMax, cnt, adj, submin, submax);
		mx=max(mx, submax[u]);
		mn=min(mn, submin[u]);
	}
	
	if(isMax){
		labels[ver]=submax[ver]=mx+1;
		submin[ver]=mn;
		if(mx+1>=cnt) cnt=mx+2;
	}
	else{
		labels[ver]=submin[ver]=mn-1;
		submax[ver]=mx;
	}
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n);
	vector<vector<int>> adj(n);
	vector<int> submin(n), submax(n);
	
	for(int i=0;i<n-1;i++){
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
	}
	
	int aux=0;
	build(0, -1, labels, 0, aux, adj, submin, submax);
	
	vector<pii> proc;
	for(int i=0;i<n;i++) proc.pb({labels[i], i});
	
	sort(all(proc));
	
	//~ for(int i=0;i<n;i++) cout << labels[i] << " \n"[i==n-1];
	
	for(int i=0;i<n;i++) labels[proc[i].se]=i;
	
	//~ for(int i=0;i<n;i++) cout << labels[i] << " \n"[i==n-1];
	
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	sort(all(c));
	
	if(c[0]<s){
		if((int)c.size()==1 || t>s || t<c[1]) return c[0];
		for(int i=(int)c.size()-1;i>=0;i--)
			if(t>=c[i]) return c[i];
	}
	else{
		reverse(all(c));
		if((int)c.size()==1 || t<s || t>c[1]) return c[0];
		for(int i=(int)c.size()-1;i>=0;i--)
			if(t<=c[i]) return c[i];
	}
	
	return -1;
}

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