Submission #429950

#	Time	Username	Problem	Language	Result	Execution time	Memory
429950		Blagojce	Rail (IOI14_rail)	C++11	30 / 100	443 ms	98728 KiB

rail

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
 
mt19937 _rand(time(NULL));
const int mxn = 5005;

#include "rail.h"

int d[mxn][mxn];
vector<pair<int,int> > g[mxn];
/*
int getDistance(int i, int j){
	return d[i][j];
}*/

int s[mxn];
int l[mxn];

bool vis[mxn];

void dfs(int u, int pos, int shape){
	vis[u] = true;
	
	s[u] = shape;
	l[u] = pos;
	
	for(auto e : g[u]){
		if(vis[e.st]) continue;
		
		int v = e.st;
		int w = e.nd;
		if(shape == 1){
			dfs(v, pos + w, 2);
		}
		else{
			dfs(v, pos - w, 1);
		}
	}
}

void findLocation(int N, int first, int location[], int stype[]){
	fr(i, 0, N){
		fr(j, 0, i){
			d[i][j] = d[j][i] = getDistance(i, j);
		}
	}
	fr(i, 0, N){
		int minD = 1e9;
		int parent = 0;
		fr(j, 0, N){
			if(i == j) continue;
			
			if(d[i][j] < minD){
				minD = d[i][j];
				parent = j;
			}
		}
		g[parent].pb({i, minD});
	}
	dfs(0, first, 1);
	fr(i, 0, N){
		stype[i] = s[i];
		location[i] = l[i];
	}
}

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