Submission #795413

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

towns

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

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

    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-g.size();
        if(cntleft>n/2 || cntright>n/2) continue;

        vector<bool> vis(n, false);
        int open=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 = getDistance(v, u);

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

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

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

    return balanced_hub;
}

int hubDistance(int n, int sub) {

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

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

    int b=0;
    vector<int> dista(n);
    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;
        }
    }

    vector<int> distb(n);
    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, dista);
    }

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

Compilation message (stderr)

towns.cpp: In function 'bool balancedSlow(int, int, int, std::map<int, std::vector<int> >&, std::vector<int>&)':
towns.cpp:15:33: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   15 |         int cntright = n-cntleft-g.size();
      |                        ~~~~~~~~~^~~~~~~~~
towns.cpp:19:24: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   19 |         int open=g.size();
      |                  ~~~~~~^~
towns.cpp:48:31: warning: conversion from 'std::map<int, std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   48 |         cntleft += group.size();
      |                               ^

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