Submission #398082

#	Time	Username	Problem	Language	Result	Execution time	Memory
398082		phathnv	Rail (IOI14_rail)	C++11	30 / 100	512 ms	98708 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);
    int a = 0, b = 0;
    for(int i = 0; i < n; i++)
        if (stype[i] && location[i] > location[b])
            b = i;
    for(int i = 0; i < n; i++)
        if (!stype[i] && min(dist[i][a], dist[i][b]) < dist[a][b]){
            if (dist[i][b] < dist[i][a]){
                location[i] = location[b] - dist[i][b];
                stype[i] = 1;
            } else {
                location[i] = location[a] + dist[i][a];
                stype[i] = 2;
            }
        }
    while (true){
        int u = b;
        for(int i = 0; i < n; i++)
            if (!stype[i] && dist[i][b] < dist[i][a] && dist[u][b] > dist[i][b])
                u = i;
        if (u != b){
            location[u] = location[b] - dist[u][b];
            Dfs(u, 1, location, stype);
        } else {
            break;
        }
    }
    while (true){
        int u = a;
        for(int i = 0; i < n; i++)
            if (!stype[i] && dist[i][a] < dist[i][b] && dist[u][a] > dist[i][a])
                u = i;
        if (u != a){
            location[u] = location[a] + dist[u][a];
            Dfs(u, 2, location, stype);
        } else {
            break;
        }
    }
}

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