Submission #986611

#	Time	Username	Problem	Language	Result	Execution time	Memory
986611		CSQ31	Stations (IOI20_stations)	C++17	76 / 100	607 ms	1688 KiB

stations

#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>adj[1000];
int tin[1000],tout[1000],color[1000];
int timer = -1;
void dfs(int v,int u){
	tin[v] = ++timer;
	for(int x:adj[v]){
		if(x==u)continue;
		color[x] = color[v]^1;
		dfs(x,v);
	}
	tout[v] = ++timer;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	for(int i=0;i<n;i++)adj[i].clear();
	vector<int>lab(n);
	for(int i=0;i+1<n;i++){
		adj[v[i]].push_back(u[i]);
		adj[u[i]].push_back(v[i]);
	}

	timer = -1;
	dfs(0,-1);
	for(int i=0;i<n;i++){
		if(color[i])lab[i] = tin[i];
		else lab[i] = tout[i];
	} 
	return lab;
}

int find_next_station(int s, int t, vector<int> c) {
	int n = c.size();
	if(c.back() > s){ 
		//s label is tin
		int last = s;
		for(int i=0;i+1<n;i++){
			int l = last+1;
			int r = c[i];
			if(l <= t && t <= r)return c[i];
			last = c[i];
		} 
		return c.back();
	}else{
		//s label is tout
		int last = s;
		for(int i=n-1;i>0;i--){
			int l = c[i];
			int r = last-1;
			if(l <= t && t <= r)return c[i];
			last = c[i];
		}
		return c[0];
	}
}

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