Submission #393945

#	Time	Username	Problem	Language	Result	Execution time	Memory
393945		Osama_Alkhodairy	Rail (IOI14_rail)	C++17	56 / 100	964 ms	98628 KiB

rail

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

const int N = 5001;

int n, dist[N][N];
vector <int> loc, type;

int ask(int x, int y){
    if(x == y) return 0;
    if(y < x) swap(x, y);
    if(dist[x][y] == -1) dist[x][y] = getDistance(x, y);
    return dist[x][y];
}
void solvel(vector <int> l, int d){
    set <int> all(l.begin(), l.end());
    while(all.size()){
        int C = -1;
        for(auto &i : all){
            if(C == -1 || ask(i, d) < ask(C, d)){
                C = i;
            }
        }
        type[C] = 1;
        loc[C] = loc[d] - ask(C, d);
        all.erase(C);
        int D = -1;
        for(auto &i : all){
            if(D == -1 || ask(i, C) < ask(D, C)){
                D = i;
            }
        }
        if(D == -1 || ask(C, D) >= ask(C, d)){
            continue;
        }
        d = D;
        type[D] = 2;
        loc[D] = loc[C] + ask(D, C);
        all.erase(D);
        vector <int> to_remove;
        for(auto &i : all){
            if(ask(C, i) < ask(D, i)){
                type[i] = 2;
                loc[i] = loc[C] + ask(i, C);
                to_remove.push_back(i);
            }
        }
        for(auto &i : to_remove){
            all.erase(i);
        }
    }
}
void solver(vector <int> r, int c){
    set <int> all(r.begin(), r.end());
    while(all.size()){
        int D = -1;
        for(auto &i : all){
            if(D == -1 || ask(i, c) < ask(D, c)){
                D = i;
            }
        }
        type[D] = 2;
        loc[D] = loc[c] + ask(c, D);
        all.erase(D);
        int C = -1;
        for(auto &i : all){
            if(C == -1 || ask(i, D) < ask(C, D)){
                C = i;
            }
        }
        if(C == -1 || ask(C, D) >= ask(c, D)){
            continue;
        }
        c = C;
        type[C] = 1;
        loc[C] = loc[D] - ask(C, D);
        all.erase(C);
        vector <int> to_remove;
        for(auto &i : all){
            if(ask(i, D) < ask(i, C)){
                type[i] = 1;
                loc[i] = loc[D] - ask(i, D);
                to_remove.push_back(i);
            }
        }
        for(auto &i : to_remove){
            all.erase(i);
        }
    }
}
void findLocation(int N, int first, int location[], int stype[]){
    if(N == 1){
        stype[0] = 1;
        location[0] = first;
        return;
    }
    n = N;
    loc.assign(n, 0);
    type.assign(n, 0);
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++){
            dist[i][j] = -1;
        }
    }
    loc[0] = first;
    type[0] = 1;
    int d = -1;
    for(int i = 1 ; i < n ; i++){
        if(d == -1 || ask(0, i) < ask(0, d)){
            d = i;
        }
    }
    type[d] = 2;
    loc[d] = loc[0] + ask(0, d);
    int c = -1;
    for(int i = 0 ; i < n ; i++){
        if(i == d) continue;
        if(c == -1 || ask(i, d) < ask(c, d)){
            c = i;
        }
    }
    type[c] = 1;
    loc[c] = loc[d] - ask(c, d);
    vector <int> l, r;
    for(int i = 0 ; i < n ; i++){
        if(i == c || i == d) continue;
        if(ask(d, i) < ask(c, i)) l.push_back(i);
        else r.push_back(i);
    }
    solvel(l, d);
    solver(r, c);
    for(int i = 0 ; i < n ; i++){
        location[i] = loc[i];
        stype[i] = type[i];
    }
}

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