제출 #303916

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
303916		fivefourthreeone	도시들 (IOI15_towns)	C++17	컴파일 에러	0 ms	0 KiB

towns

//#include "towns.h"
#include <bits/stdc++.h>

using namespace std;

const int mxN = 111;
int arr[mxN];
int dist[mxN][mxN];
int numHub = 0;
int lcadist[mxN];
int n;
int s, t;
/*int indist[mxN][mxN];
int queries = 0;
int getDistance(int a, int b) {
    queries++;
    return indist[a][b];
}*/
int getdist(int a, int b) {
    if(a==b)return 0;
    if(dist[a][b]==-1) {
        return dist[a][b] = dist[b][a] = getDistance(a, b);
    }
    return dist[a][b];
}
bool solve(int hub) {
    vector<int> stk;
    vector<int> dead;
    int dsu[mxN];
    int sz[mxN];
    for(int i = 0; i < n; ++i) {
        dsu[i] = i;
        sz[i] = 1;
        stk.push_back(i);
    }
    function<int(int)> find = [&](int a) {
        return a==dsu[a] ? a : dsu[a] = find(dsu[a]);
    };
    function<void(int, int)> merge = [&](int a, int b) {
        a = find(a); b = find(b);
        if(a==b)return;
        dsu[b] = a;
        sz[a]+=sz[b];
    };
    function<bool(int, int)> compare = [&](int a, int b) {
        if(lcadist[a] < lcadist[hub] && lcadist[b] < lcadist[hub]) {
            return true;
        }else if(lcadist[a] > lcadist[hub] && lcadist[b] > lcadist[hub]) {
            return true;   
        }else if(lcadist[a] == lcadist[hub] && lcadist[b] == lcadist[hub]) {
            if(getdist(s, a) + getdist(s, b) - getdist(a, b) > 2 * lcadist[hub])return true;
        }
        return false;
    };
    while(stk.size() > 1) {
        if(stk.size()&1) {
            dead.push_back(stk.back());
            stk.pop_back();
            continue;
        }
        int first = stk.back();
        stk.pop_back();
        int second = stk.back();
        stk.pop_back();
        if(compare(first, second)) {
            stk.push_back(first);
            merge(first, second);
        }else {
            dead.push_back(first);
            dead.push_back(second);
        }
    }
    if(stk.size()) {
        int maj = stk.back();
        for(int k: dead) {
            if(compare(maj, k)) {
                merge(maj, k);
            }
        }
        if(sz[maj] > n/2)return false;
    }
    return true;
}
int hubDistance(int N, int sub) {
    n = N;
    memset(dist, -1, sizeof(dist));
    for(int i = 1, mxdist = 0; i < n; ++i) {
        if(getdist(0, i) > mxdist) {
            mxdist = getdist(0, i);
            s = i;
        }
    }
    for(int i = 0, mxdist = 0; i < n; ++i) {
        if(i^s) {
            if(getdist(s, i) > mxdist) {
                mxdist = getdist(s, i);
                t = i;
            }
        }
    }
    int hub[2];
    int hubcnt = 0;
    int R = 0x3f3f3f3f;
    for(int i = 0; i < n; ++i) {
        lcadist[i] = (getdist(s, i) + getdist(s, 0) - getdist(i, 0)) / 2;
        if(max(lcadist[i], getdist(s, t) - lcadist[i]) < R) {
            R = max(lcadist[i], getdist(s, t) - lcadist[i]);
            hubcnt = 1;
            hub[0] = i;
        }else if(max(lcadist[i], getdist(s, t) - lcadist[i]) == R){
            hubcnt = 2;
            hub[1] = i;
        }
    }
    if(sub <= 2) {
        return R;
    }
    bool balanced = false;
    for(int i = 0; i < hubcnt; ++i) {
        balanced |= solve(hub[i]);
    }
    return (balanced ? 1 : -1) * R;
}
/*int subtask, T, realn;
int main() {
    //freopen("file.out", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    cin>>subtask>>T;
    while(T--) {
        cin>>realn;
        for(int i = 0; i < realn; ++i) {
            for(int j = 0; j < realn; ++j) {
                cin>>indist[i][j];
            }
        }
        cout<<hubDistance(subtask, realn)<<"\n";
    }
    cout<<"queries used: "<<queries<<"\n";
    return 0;
}*/

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

towns.cpp: In function 'int getdist(int, int)':
towns.cpp:22:42: error: 'getDistance' was not declared in this scope
   22 |         return dist[a][b] = dist[b][a] = getDistance(a, b);
      |                                          ^~~~~~~~~~~