Submission #396868

#	Time	Username	Problem	Language	Result	Execution time	Memory
396868		peuch	Rail (IOI14_rail)	C++17	30 / 100	1290 ms	262148 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
using namespace std;

int dist[5010][5010];
	
void dfs(int cur, int pai, int N, int marc[], int location[], int stype[]);

void findLocation(int N, int first, int location[], int stype[])
{
	int marc[N];
	
	location[0] = first, stype[0] = 1;
	
	for(int i = 0; i < N; i++)
		for(int j = i + 1; j < N; j++)
			dist[i][j] = dist[j][i] = getDistance(i, j), marc[i] = 0, marc[j] = 0;
	dfs(0, 0, N, marc, location, stype);
	return;
}

void dfs(int cur, int pai, int N, int marc[], int location[], int stype[]){
	marc[cur] = 1;
	set<pair<int, int> > aux;
	for(int i = 0; i < N; i++)
		if(i != cur) aux.insert(make_pair(dist[cur][i], i));
	while(!aux.empty()){
		int viz = aux.begin()->second;
		aux.erase(aux.begin());
		if(viz == pai) continue;
		if(marc[viz]) continue;
		if(dist[cur][viz] > dist[pai][viz]) continue;
		if(stype[cur] == 1) location[viz] = location[cur] + dist[cur][viz], stype[viz] = 2;
		else location[viz] = location[cur] - dist[cur][viz], stype[viz] = 1;
		dfs(viz, cur, N, marc, location, stype);
	}
}

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44