oj.uz

Submission #320664

# Submission time Handle Problem Language Result Execution time Memory
320664 2020-11-09T12:47:13 Z lohacho Rail (IOI14_rail) C++14
100 / 100
 123 ms 39524 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 36324 KB Output is correct
2 Correct 112 ms 36580 KB Output is correct
3 Correct 106 ms 37092 KB Output is correct
4 Correct 102 ms 37092 KB Output is correct
5 Correct 114 ms 37732 KB Output is correct
6 Correct 119 ms 38628 KB Output is correct
7 Correct 107 ms 38116 KB Output is correct
8 Correct 105 ms 37476 KB Output is correct
9 Correct 118 ms 37732 KB Output is correct
10 Correct 108 ms 37000 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 36456 KB Output is correct
2 Correct 104 ms 36580 KB Output is correct
3 Correct 104 ms 37220 KB Output is correct
4 Correct 111 ms 37092 KB Output is correct
5 Correct 104 ms 37608 KB Output is correct
6 Correct 103 ms 38624 KB Output is correct
7 Correct 105 ms 37988 KB Output is correct
8 Correct 105 ms 37472 KB Output is correct
9 Correct 114 ms 37604 KB Output is correct
10 Correct 107 ms 36964 KB Output is correct
11 Correct 103 ms 37732 KB Output is correct
12 Correct 103 ms 39524 KB Output is correct
13 Correct 103 ms 37988 KB Output is correct
14 Correct 102 ms 35560 KB Output is correct
15 Correct 103 ms 37348 KB Output is correct
16 Correct 107 ms 35940 KB Output is correct
17 Correct 107 ms 38372 KB Output is correct
18 Correct 123 ms 37348 KB Output is correct
19 Correct 104 ms 38176 KB Output is correct
20 Correct 104 ms 38372 KB Output is correct