Submission #815124

#	Time	Username	Problem	Language	Result	Execution time	Memory
815124		oscar1f	Stations (IOI20_stations)	C++17	0 / 100	668 ms	592 KiB

stations

#include "stations.h"
#include<bits/stdc++.h>

using namespace std;

const int MAX_SOM=1005;
int dv[MAX_SOM];
vector<int> adja[MAX_SOM];
vector<int> ordre;

void DFS(int pos,int prof) {
	if (dv[pos]==0) {
		dv[pos]=1;
		if (prof%2==0) {
			ordre.push_back(pos);
		}
		for (int j:adja[pos]) {
			DFS(j,prof+1);
		}
		if (prof%2==1) {
			ordre.push_back(pos);
		}
	}
}

vector<int> label(int n,int k,vector<int> u,vector<int> v) {
	int nbSom=n;
	for (int i=0;i<nbSom-1;i++) {
		adja[u[i]].push_back(v[i]);
		adja[v[i]].push_back(u[i]);
	}
	DFS(0,0);
	vector<int> label(n);
	for (int i=0;i<nbSom;i++) {
		label[ordre[i]]=i;
	}
	/*for (int i=0;i<nbSom;i++) {
		cout<<i<<" : "<<label[i]<<endl;
	}*/
	return label;
}

int find_next_station(int pos,int obj,vector<int> possi) {
	return possi[0];
	if (possi.size()==1) {
		return possi[0];
	}
	vector<int> inf,sup;
	for (int i:possi) {
		if (i<pos) {
			inf.push_back(i);
		}
		else {
			sup.push_back(i);
		}
	}
	if (pos==0) {
		for (int i:sup) {
			if (i>=obj) {
				return i;
			}
		}
	}
	if (inf.empty()) {
		for (int i=0;i<(int)sup.size()-1;i++) {
			if (sup[i]>=obj and pos<obj) {
				return sup[i];
			}
		}
		return sup.back();
	}
	else {
		for (int i=(int)inf.size()-1;i>0;i--) {
			if (inf[i]<=obj and pos>obj) {
				return inf[i];
			}
		}
		return inf[0];
	}
}

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