Submission #398068

#	Time	Username	Problem	Language	Result	Execution time	Memory
398068		phathnv	Rail (IOI14_rail)	C++11	30 / 100	453 ms	98504 KiB

rail

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

using namespace std;

const int N = 5000;

int dist[N][N];
vector<int> adj[N];

void Dfs(int u, int type, int location[], int stype[]){
    assert(stype[u] != 3 - type);
    if (stype[u])
        return;
    stype[u] = type;
    for(int v : adj[u]){
        location[v] = location[u] + (type == 1? dist[u][v] : -dist[u][v]);
        Dfs(v, 3 - type, location, stype);
    }
}

void findLocation(int n, int first, int location[], int stype[]){
    for(int i = 0; i < n; i++){
        dist[i][i] = 1e9;
        for(int j = i + 1; j < n; j++)
            dist[i][j] = dist[j][i] = getDistance(i, j);
    }
    for(int u = 0; u < n; u++){
        int v = 0;
        for(int i = 0; i < n; i++)
            if (dist[u][v] > dist[u][i])
                v = i;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 0; i < n; i++)
        stype[i] = 0;
    location[0] = first;
    Dfs(0, 1, location, stype);
}

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