Submission #287107

#	Time	Username	Problem	Language	Result	Execution time	Memory
287107		egekabas	Rail (IOI14_rail)	C++14	30 / 100	511 ms	99628 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int d[5009][5009];
int vis[5009];
set<pii> bef;
int n;

void dfs(int v, int l, int t, int loc[], int stype[]){
    stype[v] = t;
    loc[v] = l;
    if(t == 1){
        vis[v] = 1;
        bef.insert({l, v});
    }
    pii mini = {1e9, 1e9};
    for(int i = 0; i < n; ++i)
        if(!vis[i] && i != v)
            mini = min(mini, {d[v][i], i});
    //cout << v << ' ' << l << ' ' << t << ' ' << mini.ff << ' ' << mini.ss << '\n';

    if(mini.ff == 1e9) 
        return;
    if(t == 1){
        dfs(mini.ss, l+mini.ff, 2, loc, stype);
        return;
    }
    auto it = bef.lower_bound({l, 0});
    if(it != bef.begin()){
        --it;
        if(mini.ff == l-it->ff+d[it->ss][mini.ss]){
            vis[v] = 1;
            dfs(mini.ss, it->ff+d[it->ss][mini.ss], 2, loc, stype);
            return;
        }
    }
    dfs(mini.ss, l-mini.ff, 1, loc, stype);
}
void findLocation(int N, int first, int location[], int stype[]){
    //cout << '\n';
    n = N;
    for(int i = 0; i < n; ++i)
        for(int j = i+1; j < n; ++j)
            d[i][j] = d[j][i] = getDistance(i, j);
    dfs(0, first, 1, location, stype);
    //cout << '\n';
    //for(int i = 0; i < n; ++i)
    //    cout << stype[i] << ' ' << location[i] << '\n';
}

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