Submission #108140

#	Time	Username	Problem	Language	Result	Execution time	Memory
108140		PeppaPig	Towns (IOI15_towns)	C++14	0 / 100	34 ms	532 KiB

towns

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

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 205;

int u, v;
int d[N][N], branch[N];

int 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); 
}

int hubDistance(int n, int sub) {
    //Find 2 farthest nodes
    for(int i = 1; i < n; i++) if(get(0, i) > get(0, u)) u = i;
    for(int i = 1; i < n; i++) if(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) ans = min(ans, max(pos, get(u, v) - pos));
    for(int pos : hub) if(max(pos, get(u, v) - pos) == ans) swap(pos, rot), swap(pos, rot2);

    //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, 0);
    for(int i = 0; i < n; i++) {
        if(!cnt) last = i, ++cnt;
        else if(same(last, i)) ++cnt, col[i] = 1;
        else --cnt, col[i] = 2;
    }
    if(!cnt) return ans;
    bool valid = false;
    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;

    return -ans;
}

Compilation message (stderr)

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

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