Submission #795420

#	Time	Username	Problem	Language	Result	Execution time	Memory
795420		jasmin	Towns (IOI15_towns)	C++17	25 / 100	15 ms	484 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, 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 - (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
    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:26:91: warning: declaration of 'dista' shadows a global declaration [-Wshadow]
   26 | bool balancedSlow(int n, int r, int diameter, map<int, vector<int> >& group, vector<int>& dista){
      |                                                                              ~~~~~~~~~~~~~^~~~~
towns.cpp:8:13: note: shadowed declaration is here
    8 | vector<int> dista;
      |             ^~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:81:17: warning: declaration of 'dist0' shadows a global declaration [-Wshadow]
   81 |     vector<int> dist0(n);
      |                 ^~~~~
towns.cpp:5:13: note: shadowed declaration is here
    5 | vector<int> dist0;
      |             ^~~~~
towns.cpp:82:9: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   82 |     int a=1;
      |         ^
towns.cpp:7:5: note: shadowed declaration is here
    7 | int a=-1;
      |     ^
towns.cpp:91:9: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   91 |     int b=0;
      |         ^
towns.cpp:10:5: note: shadowed declaration is here
   10 | int b=-1;
      |     ^
towns.cpp:92:17: warning: declaration of 'dista' shadows a global declaration [-Wshadow]
   92 |     vector<int> dista(n);
      |                 ^~~~~
towns.cpp:8:13: note: shadowed declaration is here
    8 | vector<int> dista;
      |             ^~~~~
towns.cpp:104:17: warning: declaration of 'distb' shadows a global declaration [-Wshadow]
  104 |     vector<int> distb(n);
      |                 ^~~~~
towns.cpp:11:13: note: shadowed declaration is here
   11 | vector<int> distb;
      |             ^~~~~

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