Submission #610703

#	Time	Username	Problem	Language	Result	Execution time	Memory
610703		Mounir	Stations (IOI20_stations)	C++14	36.32 / 100	1111 ms	776 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 temps = 0;
bool vu[N];
vector<int> voisins[N];

void dfs(int noeud){
	vu[noeud] = true;
	deb[noeud] = temps++;

	for (int voisin : voisins[noeud]){
		if (vu[voisin]) continue;
		dfs(voisin);
	}
	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);
	vector<int> labels(nNoeuds);
	for (int i  = 0; i < nNoeuds; ++i)
		labels[i] = deb[i] * N + fin[i];
	return labels;
}

int find_next_station(int source, int dest, vector<int> voisins) {
	int debSource = source/N, finSource = source%N;
	int debDest = dest/N, finDest = dest%N;

	vector<pii> inters;
	for (int i = 0; i < sz(voisins); ++i)
		inters.pb({voisins[i]/N, voisins[i]%N});
	
	int iPere = -1;
	for (int i = 0; i < sz(voisins); ++i){
		if (inters[i].x <= debSource && finSource <= inters[i].y){
			iPere = i;
			continue; //si on est sur le pere
		}
		if (inters[i].x <= debDest && finDest <= inters[i].y) 
			return voisins[i];
	}
	return voisins[iPere];
}

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