Submission #1230241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230241		coco2311	Stations (IOI20_stations)	C++17	52.32 / 100	308 ms	588 KiB

stations

#include "stations.h"
#include <vector>
#include <iostream>
using namespace std;

vector<vector<int>> adj;
vector<bool> vis;
vector<int> lab;

int cnt;

void dfs(int n){
	cnt++;
	vis[n]=true;
	lab[n]=cnt*1000;
	for(int i: adj[n]){
		if(vis[i])continue;
		dfs(i);
	}
	lab[n]+=cnt;
}


vector<int> label(int N, int K, std::vector<int> u, std::vector<int> v) {
	adj.clear();
	vis.clear();
	adj.resize(N,{});
	for(int i=0;i<N-1;i++){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	cnt=-1;
	vis.resize(N,false);
	lab.resize(N);
	dfs(0);
	return lab;
}

bool ch(int a,int b){ // is a included in b
	if(a%1000<=b%1000 && a/1000>=b/1000){
		return true;
	}
	return false;
}

int find_next_station(int s, int t, std::vector<int> c) {
	if (c.size()==1){
		return c[0];
	}
	if(ch(t,s)){
		for(int i: c){
			if(ch(t,i)&&!ch(s,i)){
				return i;
			}
		}
	}
	else{
		for(int i: c){
			if(ch(s,i)){
				return i;
			}
		}
	}
	return 0;
}

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