Submission #795424

#	Time	Username	Problem	Language	Result	Execution time	Memory
795424		jasmin	Towns (IOI15_towns)	C++17	25 / 100	12 ms	356 KiB

towns

#include "towns.h"
#include<bits/stdc++.h>
using namespace std;

vector<int> dist0;

int a=-1;
vector<int> dista;

int b=-1;
vector<int> distb;

int Distance(int i, int j){
    if(j<i) swap(i, j);

    if(i==0) return dist0[j];
    if(i==a) return dista[j];
    if(i==b) return distb[j];

    if(j==a) return dista[i];
    if(j==b) return distb[i];

    return getDistance(i, j);
}

bool balancedSlow(int n, int r, int diameter, map<int, vector<int> >& group){

    bool balanced_hub=false;
    int cntleft=1;

    for(auto [x, g]: group){
        if(max(x, diameter-x)!=r){ //no hub
            continue;
        }

        int cntright = n - cntleft - (int)g.size();
        if(cntleft>n/2 || cntright>n/2) continue;

        vector<bool> vis(n, false);
        int open = (int)g.size();
        bool balanced=true;

        while(open > n/2){

            int v=g.back(); g.pop_back();
            if(vis[v]){
                continue;
            }
            vis[v]=true;

            int size=1;
            for(auto u: g){
                int d = Distance(v, u);

                if(d < dista[v]-x + dista[u]-x){ //same component
                    vis[u]=true;
                    size++;
                }
            }

            if(size > n/2){
                balanced = false;
                break;
            }
            open -= size;
        }

        if(balanced){
            balanced_hub = true;
            break;
        }
        cntleft += (int)group.size();
    }

    return balanced_hub;
}


int hubDistance(int n, int sub) {

    //find diameter
    dist0.assign(n, 0);
    a=1;
    for(int i=1; i<n; i++){
        dist0[i] = getDistance(0, i);

        if(dist0[i]>dist0[a]){
            a=i;
        }
    }

    b=0;
    dista.assign(n, 0);
    dista[0] = dist0[a];
    for(int i=1; i<n; i++){
        if(i==a) continue;

        dista[i] = getDistance(a, i);

        if(dista[i] > dista[b]){
            b=i;
        }
    }

    distb.assign(n, 0);
    distb[0] = dist0[b];
    distb[a] = dista[b];
    for(int i=1; i<n; i++){
        if(i==a || i==b) continue;

        distb[i] = getDistance(b, i);
    }

    int diameter = dista[b];



    //group the leafes
    vector<int> dleft(n); dleft[a]=0; dleft[b]=diameter;
    vector<int> ddiam(n); ddiam[a]=ddiam[b]=0;

    map<int, vector<int> > group;
    for(int i=0; i<n; i++){
        if(i==a || i==b) continue;

        ddiam[i] = (dista[i]+distb[i] - diameter)/2;
        dleft[i] = dista[i]-ddiam[i];

        group[dleft[i]].push_back(i);
    }



    //compute r
    
    int r=diameter;
    for(auto [x, g]: group){

        r = min(r, max(x, diameter-x));
    }

    bool balanced = false;
    if(2<sub){
        balanced = balancedSlow(n, r, diameter, group);
    }

    if(balanced){
        return r;
    }
    return -r;
}

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