Submission #788062

#	Time	Username	Problem	Language	Result	Execution time	Memory
788062		alvingogo	Rail (IOI14_rail)	C++14	100 / 100	58 ms	1540 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

map<pair<int,int>,int> m;
int get(int a,int b){
    if(a>b){
        swap(a,b);
    }
    if(a==b){
        return 0;
    }
    if(m.find(pair<int,int>(a,b))==m.end()){
        m[pair<int,int>(a,b)]=getDistance(a,b);
    }
    return m[{a,b}];
}
void findLocation(int n, int fr, int l[], int s[]){
    vector<int> d0(n),d1(n);
    int mn=-1;
    for(int i=1;i<n;i++){
        d0[i]=get(0,i);
        if(mn==-1 || d0[i]<d0[mn]){
            mn=i;
        }
    }
    l[0]=fr;
    s[0]=1;
    l[mn]=fr+d0[mn];
    s[mn]=2;
    vector<int> d;
    vector<pair<int,int> > a,b;
    for(int i=0;i<n;i++){
        d1[i]=get(mn,i);
        if(i==mn || i==0){
            continue;
        } 
        if(d0[i]==d1[i]+d0[mn]){
            if(d1[i]<d0[mn]){
                l[i]=l[mn]-d1[i];
                s[i]=1;
                d.push_back(-l[i]);
            }
            else{
                a.push_back({d1[i],i});
            }
        }
        else{
            b.push_back({d0[i],i});
        }
    }
    //b -> right, a -> left
    d.push_back(-l[0]);
    sort(a.begin(),a.end());
    {
        int u=0;
        for(auto h:a){
            int x=get(u,h.sc);
            int f=l[u]+x;
            int y=-(*lower_bound(d.begin(),d.end(),-f));
            if(y==f || h.fs!=f+l[mn]-2*y){
                l[h.sc]=l[mn]-d1[h.sc];
                s[h.sc]=1;
                d.push_back(-l[h.sc]);
                u=h.sc;
            }
            else{
                s[h.sc]=2;
                l[h.sc]=f;
            }
        }
    }
    sort(b.begin(),b.end());
    {
        int u=mn;
        vector<int> c;
        c.push_back(l[mn]);
        for(auto h:b){
            int x=get(u,h.sc);
            int f=l[u]-x;
            int y=*lower_bound(c.begin(),c.end(),f);
            if(y==f || h.fs!=2*y-l[0]-f){
                l[h.sc]=l[0]+d0[h.sc];
                s[h.sc]=2;
                c.push_back(l[h.sc]);
                u=h.sc;
            }
            else{
                s[h.sc]=1;
                l[h.sc]=f;
            }
        }
    }
}

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