Submission #1011848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011848		hotboy2703	Towns (IOI15_towns)	C++17	25 / 100	9 ms	492 KiB

towns

#include "towns.h"

#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 120;
ll dist[2][MAXN];
ll sus[MAXN];
ll n;
ll get_dist(ll u,ll d[]){
    ll res = 0;
    for (ll i = 0;i < n;i ++){
        if (i == u){
            d[u] = 0;
        }
        else{
            d[i] = getDistance(i,u);
            if (d[res] < d[i])res = i;
        }
    }
    return res;
}
int hubDistance(int N, int sub) {
    n=N;
    ll a = get_dist(0,dist[0]);
    ll b = get_dist(a,dist[1]);
    ll res = 1e9;
    ll cap = (dist[0][b] + dist[1][b] + dist[0][a])/2-dist[0][b];
    ll diameter = dist[1][b];
    vector <ll> val;
    vector <vector <ll> > path;
    for (ll i = 0;i < n;i ++){
        ll d = min((dist[0][i] + dist[1][i] + dist[0][a])/2-dist[0][i],cap+1);
        sus[i] = (dist[0][i] + dist[1][i] + dist[0][a])/2-dist[0][a];
        val.push_back(d);
    }
    sort(val.begin(),val.end());
    val.resize(unique(val.begin(),val.end())-val.begin());
    path.resize(sz(val));
    for (ll i = 0;i < n;i ++){
        ll d = min((dist[0][i] + dist[1][i] + dist[0][a])/2-dist[0][i],cap+1);
        path[lower_bound(val.begin(),val.end(),d)-val.begin()].push_back(i);
    }
    vector <ll> id;
    for (ll i = 0;i < sz(val);i ++){
        ll bruh = max(diameter - val[i],val[i]);
        if (bruh < res){
            id = {i};
            res = bruh;
        }
        else if (bruh == res)id.push_back(i);
    }
    ll root = -1;
    for (auto x:id){
        ll l,r;
        l = r = 0;
        for (ll j = 0;j < x;j ++)l += sz(path[j]);
        for (ll j = x+1;j < sz(val);j ++)r += sz(path[j]);
        if (l*2>n||r*2>n)continue;
        if (sz(path[x]) * 2 > n)root = x;
        else return res;
    }
    if (root==-1)return -res;
    auto same = [&](ll x,ll y){
        return getDistance(x,y) < sus[x] + sus[y];
    };
    vector <ll> bucket;
    vector <ll> lst;
    for (auto x:path[root]){
        if (lst.empty())lst.push_back(x);
        else if (same(x,lst.back()))bucket.push_back(x);
        else {
            lst.push_back(x);
            if (sz(bucket)){
                lst.push_back(bucket.back());
                bucket.pop_back();
            }
        }
    }
    ll pp = lst.back();
    while (sz(lst)){
        if (same(pp,lst.back())){
            if (sz(lst)==1){
                bucket.push_back(lst.back());
                lst.pop_back();
            }
            else{
                lst.pop_back();
                lst.pop_back();
            }
        }
        else{
            lst.pop_back();
            if (sz(bucket))bucket.pop_back();
            else {
                lst.clear();
                bucket.clear();
                break;
            }
        }
    }
//    ll big_comp = (sz(path[root])+sz(bucket))/2;
//    if (big_comp*2>n)res = -res;
	return res;
}

Compilation message (stderr)

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

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