제출 #637764

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
637764		qwerasdfzxcl	철로 (IOI14_rail)	C++17	30 / 100	84 ms	20576 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 s2, int pos1, int pos2, vector<int> C, int loc[], int typ[]){
    O = s1;
    sort(C.begin(), C.end(), cmp);

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

        int pos3 = pos2 - (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;
            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(s2, i)) R.push_back(i);
        else L.push_back(i);
    }

    solve(s1, s2, location[s1-1], location[s2-1], R, location-1, stype-1);
    solve(s2, s1, -location[s2-1], -location[s1-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;
}

컴파일 시 표준 에러 (stderr) 메시지

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:64:38: warning: 's2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |     for (int i=1;i<=n;i++) if (i!=s1 && i!=s2){
      |                                ~~~~~~^~~~~~~~

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