oj.uz

Submission #637771

# Submission time Handle Problem Language Result Execution time Memory
637771 2022-09-03T07:51:52 Z qwerasdfzxcl Rail (IOI14_rail) C++17
100 / 100
 95 ms 31876 KB 
#include "rail.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int ans[5050][5050], O;

int myquery(int i, int j){
    --i, --j;
    if (i==j) return 0;
    if (i>j) swap(i, j);
    return ans[i][j]?ans[i][j]:ans[i][j]=getDistance(i, j);
}

bool cmp(int i, int j){
    return myquery(O, i) < myquery(O, j);
}

void solve(int s1, int pos1, vector<int> C, int loc[], int typ[]){
    //printf("solve\n");
    O = s1;
    sort(C.begin(), C.end(), cmp);

    vector<pair<int, int>> P;
    int R, pR;
    for (auto &i:C){
        //printf(" %d %d %d %d / ", s1, s2, R, i);
        if (P.empty()){
            loc[i] = pos1 + myquery(s1, i);
            typ[i] = 2;
            P.emplace_back(i, loc[i]);
            R = i, pR = loc[i];
            continue;
        }

        int pos3 = pR - (myquery(R, i) - (myquery(s1, i)-myquery(s1, R)))/2;
        for (auto &[idx, pos]:P) if (pos==pos3){
            loc[i] = pR - myquery(R, i);
            typ[i] = 1;
            //printf("%d -> %d %d\n", i, typ[i], loc[i]);
            break;
        }

        if (typ[i]!=1){
            loc[i] = pos1 + myquery(s1, i);
            typ[i] = 2;
            P.emplace_back(i, loc[i]);

            R = i, pR = loc[i];

            //printf(" %d -> %d %d\n", i, typ[i], loc[i]);
        }
    }
}

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

    int n = N, s1 = 1, s2;
    int val = 1e9;
    for (int i=2;i<=n;i++) if (val > myquery(s1, i)) val = myquery(s1, i), s2 = i;

    location[s1-1] = first, location[s2-1] = first + val;
    stype[s1-1] = 1, stype[s2-1] = 2;

    vector<int> L, R;
    for (int i=1;i<=n;i++) if (i!=s1 && i!=s2){
        if (myquery(s1, i)==myquery(s1, s2)+myquery(s2, i)) L.push_back(i);
        else R.push_back(i);
    }

    solve(s1, location[s1-1], R, location-1, stype-1);
    solve(s2, -location[s2-1], L, location-1, stype-1);

    for (auto &i:L) location[i-1] = -location[i-1], stype[i-1] = ((stype[i-1]-1)^1)+1;
}

Compilation message

rail.cpp: In function 'void solve(int, int, std::vector<int>, int*, int*)':
rail.cpp:38:25: warning: 'pR' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |             loc[i] = pR - myquery(R, i);
      |                      ~~~^~~~~~~~~~~~~~~
rail.cpp:11:5: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
   11 |     if (i>j) swap(i, j);
      |     ^~
rail.cpp:25:9: note: 'R' was declared here
   25 |     int R, pR;
      |         ^
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:67:38: warning: 's2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |     for (int i=1;i<=n;i++) if (i!=s1 && i!=s2){
      |                                ~~~~~~^~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 19788 KB Output is correct
2 Correct 80 ms 18636 KB Output is correct
3 Correct 83 ms 22288 KB Output is correct
4 Correct 80 ms 20700 KB Output is correct
5 Correct 82 ms 22088 KB Output is correct
6 Correct 88 ms 24008 KB Output is correct
7 Correct 84 ms 28164 KB Output is correct
8 Correct 92 ms 30196 KB Output is correct
9 Correct 82 ms 19448 KB Output is correct
10 Correct 88 ms 31876 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 19792 KB Output is correct
2 Correct 76 ms 18652 KB Output is correct
3 Correct 77 ms 22216 KB Output is correct
4 Correct 82 ms 20808 KB Output is correct
5 Correct 78 ms 22092 KB Output is correct
6 Correct 83 ms 24008 KB Output is correct
7 Correct 82 ms 28152 KB Output is correct
8 Correct 81 ms 30216 KB Output is correct
9 Correct 82 ms 19584 KB Output is correct
10 Correct 92 ms 31868 KB Output is correct
11 Correct 90 ms 29560 KB Output is correct
12 Correct 86 ms 20212 KB Output is correct
13 Correct 94 ms 26620 KB Output is correct
14 Correct 79 ms 22904 KB Output is correct
15 Correct 83 ms 25980 KB Output is correct
16 Correct 95 ms 23884 KB Output is correct
17 Correct 79 ms 23044 KB Output is correct
18 Correct 85 ms 28024 KB Output is correct
19 Correct 80 ms 27388 KB Output is correct
20 Correct 79 ms 18552 KB Output is correct