Submission #1296345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296345		eri16	Stations (IOI20_stations)	C++20	0 / 100	3062 ms	2162688 KiB

stations

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

using namespace std;

vector<int> lbl;

int t=-1;

vector<vector<int>> adj(1005);

void dfs(int node, int parent){
	int tin=++t;
	for(int child : adj[node])
		if(child != parent) dfs(child,node);
	int tout=t;
	lbl[node]=tout*1000+tin;
}


vector<int> label(int n, int k, vector<int> u, vector<int> v){
    lbl.resize(n);

	for(int i=0; i<n-1; i++) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
    dfs(1,-1);
    return lbl;
}

int find_next_station(int start, int final, vector<int> rel){
	final-=(final/1000)*1000;
	int outmx=rel[rel.size()-1]/1000;

	int cur=0;
	
	while(cur<rel.size()){
		int child=rel[cur];
		
		int in=child-(child/1000)*1000;
		int out=child/1000;
		
		if(out==outmx)break;
		if(in<=final && final<=out)return child;
		cur++;
	}

	for(int  j=rel.size()-1; j>=cur; j--){
		int child=rel[j];
		int in=child-(child/1000)*1000;
		int out=child/1000;
		if(in<=final && final<=out)return child;
	}
	return rel[cur];
}

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