제출 #610791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
610791		Mounir	기지국 (IOI20_stations)	C++14	0 / 100	857 ms	676 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;
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++;
	profondeur[noeud] = etage;

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

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) {
	vector<pii> inters;
	if (voisins[0] < source){
		//on est une fin
		inters.pb({-1, 1e9});
		for (int i = 1; i < sz(voisins) - 1; ++i)
			inters.pb({voisins[i], voisins[i + 1] - 1});
		if (sz(voisins) != 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]});
		if (sz(voisins) != 1)
			inters.pb({-1, 1e9});
	}

	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: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 0 / 10
• Subtask 5: 0 / 61