Submission #813131

#	Time	Username	Problem	Language	Result	Execution time	Memory
813131		Wael	Rail (IOI14_rail)	C++14	30 / 100	1124 ms	200152 KiB

rail

#include<bits/stdc++.h>
using namespace std;
#include "rail.h"
#define F first
#define S second
typedef int ll;
int const M = 5e3 + 20;
int Dis[M][M] , mn[M] , closer[M] , cur , n;
bool vis[M];
set<ll>TypeC , TypeD;
 
bool cmp(int a , int  b) {
    return (Dis[0][a] < Dis[0][b]);
}
 
inline ll dis(int a , int b) {
    if(a == b) return 0;
    if(a > b) swap(a , b);
    return Dis[a][b];
}
 
inline ll Getbehind(int node) {
 
    int Mn = 1e9;
    for(int next = 0 ; next < n ; ++next) {
        if(dis(node , next) == mn[node] + dis(closer[node] , next) && dis(closer[node] , next) > mn[node]) {
            Mn = min(Mn , dis(node , next));
        }
    }
 
    int res = 0;
    for(int next = 0 ; next < n ; ++next) {
        if(dis(node , next) == mn[node] + dis(closer[node] , next) && dis(closer[node] , next) > mn[node]) {
            if(dis(node , next) == Mn) res = next;
        }
    }
 
    return res;
 
}
 
void findLocation(int x , int first , int location[], int stype[]) {
    n = x;
    for(int i = 0 ; i < n ; ++i) {
        mn[i] = 1e9;
        for(int j = i + 1 ; j < n ; ++j) 
            Dis[i][j] = getDistance(i , j);
        for(int j = 0 ; j < n ; ++j) {
            if(i == j) continue;
            if(dis(i , j) < mn[i]) closer[i] = j;
            mn[i] = min(mn[i] , dis(i , j));
        }
    }
 
    stype[0] = 1;
    location[0] = first;
 
    set<ll>st;
    st.insert(0);
    while(st.size()) {
        int node = *st.begin();
        st.erase(st.begin());
        if(vis[node]) continue;
        vis[node] = 1;
 
        if(stype[node] == 1) {
            int Left = Getbehind(node);
            if(Left) {
                location[Left] = location[node] + mn[node] - dis(closer[node] , Left);
                stype[Left] = 1;
                st.insert(Left);
            }
 
            location[closer[node]] = location[node] + mn[node];
            stype[closer[node]] = 2;
            st.insert(closer[node]);
        } 
 
        else {
            int Right = Getbehind(node);
            if(Right) {
                location[Right] = location[node] - mn[node] + dis(closer[node] , Right);
                stype[Right] = 2;
                st.insert(Right);
            }
 
            location[closer[node]] = location[node] - mn[node];
            stype[closer[node]] = 1;
            st.insert(closer[node]);
        }
    }
 
    for(int i = 0 ; i < n ; ++i) for(int j = 0 ; j < n ; ++j) Dis[i][j] = dis(i , j);
 
    int a = 0 , b , MinDis = 1e9;
    location[a] = first;
    stype[a] = 1;
    TypeC.insert(location[a]);
 
    for(int station = 1 ; station < n ; ++station) {
        //Dis[a][station] = getDistance(a , station);
        if(Dis[a][station] < MinDis) {
            b = station;
            MinDis = Dis[a][b];
        }
    }
 
    location[b] = location[a] + Dis[a][b];
    stype[b] = 2;
    TypeD.insert(location[b]);
 
    vector<ll>rem;
    for(int station = 1 ; station < n ; ++station) {
        if(station == b) continue;
        //Dis[b][station] = getDistance(b , station);
        rem.push_back(station);
    }
    
    sort(rem.begin() , rem.end() , cmp);
 
    int LeftMost = a , RightMost = b;
 
    for(auto station : rem) { 
        if(Dis[a][station] < Dis[b][station]) {
            //int CurDis = getDistance(RightMost , station);
            int CurDis = dis(RightMost , station);
            int Expect = location[RightMost] - CurDis;
            auto it = TypeD.lower_bound(Expect);
            if(*it - location[a] + *it - Expect == Dis[a][station] && Expect > location[b]) {
                //assert(stype[station] == 1);
                location[station] = Expect;
                stype[station] = 1;
                TypeC.insert(location[station]);
            } else {
                //assert(stype[station] == 2);
                RightMost = station;
                location[RightMost] = location[a] + Dis[a][RightMost];
                stype[RightMost] = 2;
                TypeD.insert(location[RightMost]);
            }
        }
 
        else {
            //int CurDis = getDistance(LeftMost , station);
            int CurDis = dis(LeftMost , station);
            int Expect = location[LeftMost] + CurDis;
            auto it = TypeC.lower_bound(Expect); --it;
            if(stype[station] == 2) assert(location[closer[station]] == *it);
            if(location[b] - *it + Expect - *it == Dis[b][station] && Expect < location[a]) {
                //assert(stype[station] == 2);
                location[station] = Expect;
                stype[station] = 2;
                TypeD.insert(location[station]);
            } else {
                //assert(stype[station] == 1);
                if(stype[station] != 1) return;
                LeftMost = station;
                location[LeftMost] = location[b] - Dis[b][LeftMost];
                stype[LeftMost] = 1;
                TypeC.insert(location[LeftMost]);
            }
        }
        
    }
 
    return;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:108:14: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |     location[b] = location[a] + Dis[a][b];
      |              ^

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