Submission #800490

#	Time	Username	Problem	Language	Result	Execution time	Memory
800490		FEDIKUS	Stations (IOI20_stations)	C++17	67.23 / 100	736 ms	904 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn=1010;
int t=0;
int tin[maxn];
int tout[maxn];
int res[maxn];
vector<int> g[maxn];

void dfs(int node,int d=0,int par=-1){
	tin[node]=t++;
	for(int i:g[node]){
		if(i==par) continue;
		dfs(i,d+1,node);
	}
	tout[node]=t++;
	if(d&1) res[node]=tin[node];
	else res[node]=tout[node];
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n);
	for(int i=0;i<n;i++) g[i].clear();
	for(int i=0;i<n-1;i++){
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	dfs(0);
	for(int i=0;i<n;i++) labels[i]=res[i];
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	int maxi=*max_element(c.begin(),c.end());
	vector<pair<int,int> > decoo(int(c.size())-1);
	if(maxi>s){ // on je in
		int cale=c.back();
		c.pop_back();
		for(int i=0;i<int(c.size());i++) decoo[i].second=c[i];
		int prosli=s;
		for(int i=0;i<int(c.size());i++){
			decoo[i].first=prosli+1;
			prosli=decoo[i].second;
		}
		for(int i=0;i<int(c.size());i++){
			if(decoo[i].first<=t && t<=decoo[i].second) return decoo[i].second;
		}
		return cale;
	}else{ //on je out
		int cale=c.front();
		c.erase(c.begin());
		for(int i=0;i<int(c.size());i++) decoo[i].first=c[i];
		int prosli=s;
		for(int i=int(c.size())-1;i>=0;i--){
			decoo[i].second=prosli-1;
			prosli=decoo[i].first;
		}
		for(int i=0;i<int(c.size());i++){
			if(decoo[i].first<=t && t<=decoo[i].second) return decoo[i].first;
		}
		return cale;
	}
	return c[0];
}

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