oj.uz

Submission #108141

# Submission time Handle Problem Language Result Execution time Memory
108141 2019-04-27T16:05:34 Z PeppaPig Towns (IOI15_towns) C++14
0 / 100
 27 ms 512 KB 
#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) {
        if(rot == -1) rot = pos;
        else rot2 = pos;
    }
    return ans;
 
    //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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 512 KB Output isn't correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -