Submission #320664

#	Time	Username	Problem	Language	Result	Execution time	Memory
320664		lohacho	Rail (IOI14_rail)	C++14	100 / 100	123 ms	39524 KiB

rail

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

using namespace std;

using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)5004;
vector<pair<int, int>> l, r;
int dis[5004][5004];

void findLocation(int N, int first, int location[], int stype[]){
    int rnum, mn = MOD;
    for(int i = 1; i < N; ++i){
        dis[0][i] = getDistance(0, i);
        if(dis[0][i] < mn){
            mn = dis[0][i];
            rnum = i;
        }
    }
    for(int i = 1; i < N; ++i){
        if(i == rnum){
            continue;
        }
        dis[rnum][i] = getDistance(rnum, i);
    }
    for(int i = 1; i < N; ++i){
        if(i == rnum){
            continue;
        }
        if(dis[0][i] == dis[0][rnum] + dis[rnum][i]){
            l.push_back({dis[rnum][i], i});
        }
        else{
            r.push_back({dis[0][i], i});
        }
    }
    sort(r.begin(), r.end());
    location[0] = first, stype[0] = 1;
    location[rnum] = first + dis[0][rnum], stype[rnum] = 2;
    vector<int> last;
    for(auto&i:r){
        int num = i.second;
        if(!(int)last.size()){
            location[num] = first + dis[0][num], stype[num] = 2;
            last = {num}; continue;
        }
        dis[last.back()][num] = getDistance(last.back(), num);
        int f = 0;
        for(int i = (int)last.size() - 1; i >= 0; --i){
            int ndis = dis[last.back()][num] - location[last.back()] + location[last[i]];
            if(ndis < 0){
                break;
            }
            dis[last[i]][num] = ndis;
            if(dis[0][num] == dis[0][last[i]] + dis[last[i]][num]){
                f = 1;
                location[num] = location[last[i]] - dis[last[i]][num], stype[num] = 1;
                break;
            }
        }
        if(!f){
            location[num] = first + dis[0][num], stype[num] = 2;
            last.push_back(num);
        }
    }
    sort(l.begin(), l.end());
    for(auto&i:l){
        int num = i.second;
        if(!(int)last.size()){
            location[num] = location[rnum] - dis[rnum][num], stype[num] = 1;
            last = {num};
            continue;
        }
        dis[last.back()][num] = getDistance(last.back(), num);
        int f = 0;
        for(int i = (int)last.size() - 1; i >= 0; --i){
            int ndis = dis[last.back()][num] - location[last[i]] + location[last.back()];
            if(ndis < 0){
                break;
            }
            dis[last[i]][num] = ndis;
            if(dis[rnum][num] == dis[rnum][last[i]] + dis[last[i]][num]){
                f = 1;
                location[num] = location[last[i]] + dis[last[i]][num], stype[num] = 2;
                break;
            }
        }
        if(!f){
            location[num] = location[rnum] - dis[rnum][num], stype[num] = 1;
            last.push_back(num);
        }
    }
//    for(int i = 0; i < N; ++i){
//        cout << stype[i] << ' ' << location[i] << endl;
//    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:71:59: warning: 'rnum' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |             location[num] = location[rnum] - dis[rnum][num], stype[num] = 1;
      |                                              ~~~~~~~~~~~~~^

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