Submission #320654

#	Time	Username	Problem	Language	Result	Execution time	Memory
320654		lohacho	Rail (IOI14_rail)	C++14	30 / 100	94 ms	20708 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;
    int last = -1;
    for(auto&i:r){
        int num = i.second;
        if(last == -1){
            location[num] = first + dis[0][num], stype[num] = 2;
            last = num; continue;
        }
        dis[last][num] = getDistance(last, num);
        if(dis[0][num] == dis[0][last] + dis[last][num]){
            location[num] = location[last] - dis[last][num], stype[num] = 1;
        }
        else{
            location[num] = first + dis[0][num], stype[num] = 2;
            last = num;
        }
    }
    last = -1;
    for(auto&i:l){
        int num = i.second;
        if(last == -1){
            location[num] = location[rnum] - dis[rnum][num], stype[num] = 1;
            last = num;
            continue;
        }
        dis[last][num] = getDistance(last, num);
        if(dis[rnum][num] == dis[rnum][last] + dis[last][num]){
            location[num] = location[last] + dis[last][num], stype[num] = 2;
        }
        else{
            location[num] = location[rnum] - dis[rnum][num], stype[num] = 1;
            last = num;
        }
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:40:14: warning: 'rnum' may be used uninitialized in this function [-Wmaybe-uninitialized]
   40 |     location[rnum] = first + dis[0][rnum], stype[rnum] = 2;
      |              ^~~~

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