Submission #304990

#	Time	Username	Problem	Language	Result	Execution time	Memory
304990		Wu_Ren	Stations (IOI20_stations)	C++17	100 / 100	1162 ms	952 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>ans;
int head[1010],o,cnt;
struct edge{
	int to,link;
}e[2010];
void add_edge(int u,int v){
	e[++o].to=v,e[o].link=head[u],head[u]=o;
	e[++o].to=u,e[o].link=head[v],head[v]=o;
}
void dfs(int u,int pre,int dep){
	if(dep&1) ans[u]=cnt++;
	for(int i=head[u];i;i=e[i].link){
		if(e[i].to==pre) continue;
		dfs(e[i].to,u,dep+1);
	}
	if(!(dep&1)) ans[u]=cnt++;
}
vector<int> label(int n,int k,vector<int>u,vector<int>v){
	for(int i=0;i<n;i++) head[i]=0;
	cnt=o=0,ans.clear(),ans.resize(n);
	for(int i=0;i<n-1;i++) add_edge(u[i],v[i]);
	dfs(0,-1,1);
	return ans;
}

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

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