Submission #637771

#	Time	Username	Problem	Language	Result	Execution time	Memory
637771		qwerasdfzxcl	Rail (IOI14_rail)	C++17	100 / 100	95 ms	31876 KiB

rail

#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 (stderr)

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 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44