제출 #610798

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
610798		Mounir	Stations (IOI20_stations)	C++14	100 / 100	905 ms	796 KiB

stations

#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define pb push_back
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define x first
#define y second
//#define int long long
using namespace std;

const int N = 1001, INDEFINI = -1;
const pii TOUT = {-1, 1e6};
int deb[N], fin[N];
int profondeur[N];
int temps = 0;
bool vu[N];
vector<int> voisins[N];

void dfs(int noeud, int etage){
	vu[noeud] = true;
	deb[noeud] = (temps++)/2;
	profondeur[noeud] = etage;

	for (int voisin : voisins[noeud]){
		if (vu[voisin]) continue;
		dfs(voisin, etage + 1);
	}
	fin[noeud] = (temps++)/2;
}

vector<int> label(int nNoeuds, int labelMax, vector<int> u, vector<int> v) {
	temps = 0;
	for (int noeud = 0; noeud < nNoeuds; ++noeud){
		deb[noeud] = fin[noeud] = INDEFINI;
		vu[noeud] = false;
		voisins[noeud] = {};
	}

	for (int i = 0; i < nNoeuds - 1; ++i){
		voisins[u[i]].pb(v[i]);
		voisins[v[i]].pb(u[i]);
	}
	
	dfs(0, 0);
	vector<int> labels(nNoeuds);
	for (int i = 0; i < nNoeuds; ++i){
		if (profondeur[i]%2 == 0)
			labels[i] = deb[i];
		else
			labels[i] = fin[i];
	}	
	return labels;
}

int find_next_station(int source, int dest, vector<int> voisins) {
	if (sz(voisins) == 1)
		return voisins[0];
	vector<pii> inters;
	if (voisins[0] < source){
		//on est une fin
		inters.pb(TOUT);
		for (int i = 1; i < sz(voisins) - 1; ++i)
			inters.pb({voisins[i], voisins[i + 1] - 1});
		inters.pb({voisins.back(), source - 1});
	}
	else {
		//on est un debut
		inters.pb({source + 1, voisins[0]});
		for (int i = 1; i < sz(voisins) - 1; ++i)
			inters.pb({voisins[i - 1] + 1, voisins[i]});
		inters.pb(TOUT);
	}

	int iPere = -1;
	for (int i = 0; i < sz(voisins); ++i){
		if (inters[i].x <= source && source <= inters[i].y){
			iPere = i;
			continue; //si on est sur le pere
		}
		if (inters[i].x <= dest && dest <= inters[i].y) 
			return voisins[i];
	}
	return voisins[iPere];
}

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