Submission #1042855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042855		ALeonidou	Rail (IOI14_rail)	C++17	56 / 100	308 ms	98832 KiB

rail

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

#define ll int
#define F first
#define S second
#define sz(x) (ll)x.size()
#define endl "\n"
#define pb push_back

typedef vector <ll> vi;
typedef pair <ll,ll> ii;
typedef vector <ii> vii;

#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;

void printVct(vi &v){
    for (ll i =0; i<sz(v); i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

ll n, found;
vector <vi> arr;
vi vis;

inline void visit(ll idx, ll p, ll t, ll pos[], ll type[]){
    vis[idx] = 1;
    pos[idx] = p;
    type[idx] = t;
    found++;
}

void init_left_and_right(ll &l, ll &r, vi &left, vi &right, ll pos[], ll type[]){
    // cout<<endl;
    // dbg2(l,r);
    left.clear(), right.clear();
    ll better_left_start_pos = -1;
    for (ll i =0; i<n; i++){
        if (!vis[i]){
            ll a = arr[l][i];
            ll b = arr[r][i];
            // dbg3(i,a,b);
            if (a < b){
                right.pb(i);
            }
            else{
                if (arr[l][r] > arr[r][i]){
                    //initial in between case:
                    if (better_left_start_pos == -1 || arr[better_left_start_pos][r] > arr[i][r]){
                        better_left_start_pos = i;
                    }
                }
                else{
                    left.pb(i);
                }
            }
        }
    }
    if (better_left_start_pos != -1){
        visit(better_left_start_pos, pos[r] - arr[better_left_start_pos][r], 1, pos, type);
        l = better_left_start_pos;
        init_left_and_right(better_left_start_pos,r,left,right,pos,type);
    }
}

void solve(ll &l, ll &r, ll pos[], ll type[], vi &left, vi &right){       //Time complexity: O(n)
    // dbg3(found,l,r);
    //update left
    ll miniLeft = -1, miniRight = -1;
    vi tmp_right, tmp_left;
    for (ll i =0; i<sz(left); i++){
        ll c = left[i];
        if (!vis[c]){
            tmp_left.pb(c);
            if (miniLeft == -1 || arr[l][miniLeft] > arr[l][c]){
                miniLeft = c;
            }
        }
    }
    //update right
    for (ll i =0; i<sz(right); i++){
        ll c = right[i];
        if (!vis[c]){
            tmp_right.pb(c);
            if (miniRight == -1 || arr[l][miniRight] > arr[l][c]){
                miniRight = c;
            }
        }
    }
    left = tmp_left;
    right = tmp_right;

    // cout<<"left:";
    // printVct(left);
    // cout<<"right:";
    // printVct(right);

    if (sz(left)){
        //left
        ll newLeft = miniLeft;
        ll mini_left_from_new_left = -1;
        // dbg(newLeft);
        visit(newLeft, pos[r] - arr[r][newLeft], 1, pos, type);
        for (ll i =0; i<sz(left); i++){
            if (vis[left[i]]) continue;
            if (mini_left_from_new_left == -1 || arr[newLeft][mini_left_from_new_left] > arr[newLeft][left[i]]){
                mini_left_from_new_left = left[i];
            }
        }
        // dbg(mini_left_from_new_left);
        if (mini_left_from_new_left != -1 && arr[newLeft][mini_left_from_new_left] < arr[l][mini_left_from_new_left]){
            //C2
            visit(mini_left_from_new_left, pos[newLeft] + arr[mini_left_from_new_left][newLeft], 2, pos, type);
            for (ll i =0; i<sz(left); i++){
                if (vis[left[i]]) continue;
                if (arr[left[i]][mini_left_from_new_left] > arr[left[i]][newLeft]){
                    visit(left[i], pos[newLeft] + arr[newLeft][left[i]], 2, pos, type);
                }
            }
        }
        l = newLeft; 
    }
    else{
        //right
        ll newRight = miniRight;
        ll mini_right_from_new_right = -1;
        visit(newRight, pos[l] + arr[l][newRight], 2, pos, type);
        // dbg(newRight);
        for (ll i =0; i<sz(right); i++){
            if (vis[right[i]]) continue;
            if (mini_right_from_new_right == -1 || arr[newRight][mini_right_from_new_right] > arr[newRight][right[i]]){
                mini_right_from_new_right = right[i];
            }
        }
        // dbg(mini_right_from_new_right);
        if (mini_right_from_new_right != -1 && arr[newRight][mini_right_from_new_right] < arr[r][mini_right_from_new_right]){
            //C2
            visit(mini_right_from_new_right, pos[newRight] - arr[mini_right_from_new_right][newRight], 1, pos, type);
            for (ll i =0; i<sz(right); i++){
                if (vis[right[i]]) continue;
                if (arr[right[i]][mini_right_from_new_right] > arr[right[i]][newRight]){
                    visit(right[i], pos[newRight] - arr[newRight][right[i]], 1, pos, type);
                }
            }
        }
        r = newRight; 
    }
}

void findLocation(ll N, ll f, ll pos[], ll type[])
{
    n = N;
    arr.assign(n, vi(n));
    for (ll i = 0; i<n; i++){
        for (ll j =0; j<n; j++){
            if (i == j) arr[i][j] = 0;
            else if (i > j) arr[i][j] = arr[j][i];
            else arr[i][j] = getDistance(i,j);
        }
    }
    // for (ll i =0; i<n; i++){
    //     cout<<i<<": ";
    //     for (ll j =0; j<n;j++){
    //         cout<<arr[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }

    vis.assign(n, 0);

    vii v0;
    for (ll i =1; i<n; i++){
        v0.pb(ii(arr[0][i], i));
    }
    sort(v0.begin(), v0.end());

    ll first_right = v0[0].S;

    visit(0, f, 1, pos, type);
    visit(first_right, f + v0[0].F, 2, pos, type);

    vi left, right;
    ll l = 0, r = first_right;
    init_left_and_right(l, r, left, right, pos, type);
    // dbg2(l,r);
    // cout<<endl<<endl<<endl<<endl;
    // printVct(vis);
    while (found < n){
        // cout<<endl;
        // printVct(vis);
        solve(l,r,pos,type,left,right);
        // cout<<endl;
    }

    // for (ll i =0; i<n; i++){
    //     cout<<pos[i]<<" ";
    // }
    // cout<<endl;
    // for (ll i =0; i<n; i++){
    //     cout<<type[i]<<" ";
    // }
    // cout<<endl;
}

/*
3
5
1 3
2 8
1 6
1 5
1 0

3
4
1 0
2 6
2 7
1 4

3
6
1 0
2 9
1 3
2 2
1 4
2 5

3
4
1 0
2 8
1 7
2 9

3
3
1 3
2 9
2 1

3
5
1 5
2 8
2 6
2 7
1 2

3
5
1 5
1 2
1 6
2 3
2 8

2
3
4 1
5 2
6 2

1
4
1 1
2 4
2 7
2 9

2
6
1 3
2 6
2 7
1 1
1 0
2 8



*/

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