Submission #1301397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301397		jahongir	Rail (IOI14_rail)	C++20	100 / 100	46 ms	728 KiB

rail

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define pb push_back

const int mxn = 5000, inf = 1e9;
int dist[4][mxn];

bool comp(int i, int j){
    return dist[0][i] < dist[0][j];
}


void findLocation(int N, int first, int location[], int stype[]){
    location[0] = first;
    stype[0] = 1;
    if(N==1) return;

    int piv1 = 1;
    for(int i = 1; i < N; i++){
        dist[0][i] = getDistance(0,i);
        if(dist[0][i] < dist[0][piv1])
            piv1 = i;
    }

    location[piv1] = location[0] + dist[0][piv1];
    stype[piv1] = 2;

    for(int i = 1; i < N; i++) if(i!=piv1)
        dist[1][i] = getDistance(piv1,i);

    vector<int> comp1,comp2;
    for(int i = 1; i < N; i++) if(i!=piv1){
        if(dist[1][i]+dist[0][piv1]==dist[0][i]) 
            comp1.push_back(i);
        else
            comp2.push_back(i);
    }

    sort(comp1.begin(),comp1.end(),comp);
    sort(comp2.begin(),comp2.end(),comp);
        
    if(!comp1.empty()){
        int piv = comp1[0];
        location[piv] = location[piv1] - dist[1][piv];
        stype[piv] = 1;

        set<pii> st; st.insert({location[piv],piv});
        st.insert({location[0],0});

        for(int i = 1; i < comp1.size(); i++){
            int v = comp1[i];
            int a = location[piv1] - dist[1][v];
            
            
            auto it = st.lower_bound(make_pair(a+1,-1));

            int cap = st.begin()->second;
            int req = getDistance(cap,v);
            int smt = 0;

            while(next(it) != st.end()){
                int u = it->second;

                if(2*(it->first) - next(it)->first >= a){
                    it++; continue;
                }

                if(req - (location[u]-location[cap]) + dist[1][u] == dist[1][v]){
                    location[v] = -a + 2*location[u];
                    stype[v] = 2; smt = 1;
                    break;
                }
                it++;
            }

            if(smt==0){
                location[v] = a;
                stype[v] = 1;
                st.insert({a,v});
            }
        }
    }

    if(!comp2.empty()){
        int piv = comp2[0];
        location[piv] = location[0] + dist[0][piv];
        stype[piv] = 2;

        set<pii> st; st.insert({location[piv],piv});
        st.insert({location[piv1],piv1});


        for(int i = 1; i < comp2.size(); i++){
            int v = comp2[i];
            int a = location[0] + dist[0][v];
            
            auto it = st.lower_bound(make_pair(a,-1));

            int cap = prev(st.end())->second;
            int req = getDistance(v,cap);
            
            int smt = 0;
            while(prev(it) != st.begin()){
                it--;
                if(2*(it->first) - prev(it)->first <= a) continue;

                int u = it->second;
                if(req - (location[cap]-location[u]) + dist[0][u] == dist[0][v]){
                    location[v] = -a + 2*location[u];
                    stype[v] = 1; smt = 1; break;
                }
            }

            if(smt==0){
                location[v] = a;
                stype[v] = 2;
                st.insert({a,v});
            }
        }
    }

    
}

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