제출 #108198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
108198		PeppaPig	도시들 (IOI15_towns)	C++14	35 / 100	32 ms	1152 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 205;
 
int hubDistance(int n, int sub) {
    int u = 0, v = 0;
    vector<vector<int> > d(n, vector<int>(n));
    vector<int> branch(n);

    auto get = [&](int a, int b) {
        if(a == b) return 0;
        if(d[a][b]) return d[a][b];
        return d[a][b] = d[b][a] = getDistance(a, b);
    };

    //Find 2 farthest nodes
    for(int i = 0; i < n; i++) if(i != 0 && get(0, i) > get(0, u)) u = i;
    for(int i = 0; i < n; i++) if(i != u && get(u, i) > get(u, v)) v = i;
 
    //Get hub candidates on 0-u path
    int lim = (get(0, u) + get(u, v) - get(0, v)) / 2;
    vector<int> hub;
    for(int i = 0; i < n; i++) {
        branch[i] = (get(u, i) + get(0, u) - get(0, i)) / 2;
        if(branch[i] <= lim) hub.emplace_back(branch[i]);
    }    
    sort(hub.begin(), hub.end());
    hub.resize(unique(hub.begin(), hub.end()) - hub.begin());
 
    //Find hubs
    int ans = get(u, v), rot = -1, rot2 = -1;
    for(int pos : hub) {
        int r = max(pos, get(u, v) - pos);
        if(r <= ans) {
            if(r == ans) swap(pos, rot), swap(pos, rot2);
            else rot = pos, rot2 = -1;
            ans = r;
        }
    }
 
    //Remove unbalanced one if necessary
    if(rot != -1 && rot2 != -1) {
        int sz_l = 0;
        for(int i = 0; i < n; i++) sz_l += (branch[i] <= rot);
        if(sz_l == n - sz_l) return ans;
        else if(sz_l < n - sz_l) swap(rot, rot2);
    }
    auto same = [&](int a, int b) {
        int ba = branch[a], bb = branch[b];
        if(ba == rot && bb == rot)
            return get(a, b) < get(0, a) + get(u, b) - get(0, u);
        else return (ba < rot && bb < rot) || (ba > rot && bb > rot);
    };
 
    //Boyer-Moore Majority Vote Algorithm
    int cnt = 0, last = -1, total = 0;
    vector<int> col(n);
    for(int i = 0; i < n; i++) {
        if(!cnt) last = i, ++cnt, col[i] = 0;
        else if(same(last, i)) ++cnt, col[i] = 1;
        else --cnt, col[i] = 2;
    }
    bool valid = false;
    cnt = 0;
    for(int i = 0; i < n; i++) {
        if(!col[i]) {
            ++cnt;
            if(same(i, last)) ++total, valid = true;
        } else if(col[i] == 1) ++cnt, total += valid;
        else {
            total += same(i, last);
            if(!--cnt) valid = false;
        }
    }
    if(total > n / 2) return -ans;
    else return ans;
}

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

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:8:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int n, int sub) {
                            ^~~

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39