Submission #396874

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

rail

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

const int MAXN = 5010;

int n;
map<pair<int, int>, int> dist;
int marc[MAXN], loc[MAXN], tp[MAXN];
	
void dfs(int cur, int pai);

void findLocation(int N, int first, int location[], int stype[])
{
	dist[make_pair(0, 0)] = 1e6;
	n = N;
	
	loc[0] = first, tp[0] = 1;
	
	dfs(0, 0);
	
	for(int i = 0; i < N; i++) location[i] = loc[i], stype[i] = tp[i];
	return;
}

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

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