Submission #1273538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273538		Aviansh	Rail (IOI14_rail)	C++20	56 / 100	254 ms	179784 KiB

rail

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

using namespace std;

const int maxn = 5005;

int mem[maxn][maxn];

int dist(int i, int j){
    if(mem[i][j]==-1){
        mem[i][j]=getDistance(i,j);
        mem[j][i]=mem[i][j];
    }
    return mem[i][j];
}

int fr;

void righter(int first, int lefmost, int location[], int stype[], vector<int>aval){
    if(aval.size()==0){
        return;
    }
    vector<int>dists;
    for(int i : aval){
        dists.push_back(dist(0,i));
    }
    int mni = min_element(dists.begin(),dists.end())-dists.begin();
    int mn = aval[mni];
    location[mn]=first+dists[mni];
    stype[mn]=2;
    vector<int>rig;
    for(int i : aval){
        if(i==mn){
            continue;
        }
        if(dist(0,mn)+dist(mn,i)==dist(0,i)&&first+dists[mni]-dist(mn,i)>lefmost){
            location[i]=first+dists[mni]-dist(mn,i);
            stype[i]=1;
        }
        else{
            rig.push_back(i);
        }
    }
    righter(first,location[mn],location,stype,rig);
}

void lefter(int first, int rigmost, int location[], int stype[], vector<int>aval, int init){
    if(aval.size()==0){
        return;
    }
    vector<int>dists;
    for(int i : aval){
        dists.push_back(dist(init,i));
    }
    int mni = min_element(dists.begin(),dists.end())-dists.begin();
    int mn = aval[mni];
    location[mn]=first-dists[mni];
    stype[mn]=1;
    vector<int>lef;
    for(int i : aval){
        if(i==mn){
            continue;
        }
        if(dist(init,mn)+dist(mn,i)==dist(init,i)&&first-dists[mni]+dist(mn,i)<rigmost){
            location[i]=first-dists[mni]+dist(mn,i);
            stype[i]=2;
        }
        else{
            lef.push_back(i);
        }
    }
    lefter(first,location[mn],location,stype,lef,init);
}

void findLocation(int n, int first, int location[], int stype[]) {
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            mem[i][j]=-1;
        }
    }
    location[0]=first;
    stype[0]=1;

    int dis[n];

    dis[0]=0;

    for(int i = 1;i<n;i++){
        dis[i]=dist(0,i);
    }

    fr = min_element(dis+1,dis+n)-dis;


    location[fr]=first+*min_element(dis+1,dis+n);
    stype[fr]=2;

    vector<int>rig;
    vector<int>lef;
    for(int i = 1;i<n;i++) {
        if(i==fr){
            continue;
        }
        if(dist(0,i)==dist(0,fr)+dist(fr,i)){
            lef.push_back(i);
        }
        else{
            rig.push_back(i);
        }
    }

    righter(first,location[fr],location,stype,rig);
    lefter(location[fr],location[fr],location,stype,lef,fr);

}

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