oj.uz

Submission #795513

# Submission time Handle Problem Language Result Execution time Memory
795513 2023-07-27T10:43:47 Z jasmin Towns (IOI15_towns) C++17
48 / 100
 13 ms 356 KB 
#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

            cntleft+=g.size();
            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;
}

bool balanced4(int n, int r, int diameter, map<int, vector<int> >& group){
   
    int left=1;
    for(auto [x, g]: group){

        if(r!= max(x, diameter-x)){ //no hub

            left += g.size();
            continue;
        }

        int gsize=g.size();

        int right=n-left-gsize;
        if(left<=n/2 && right<=n/2 && gsize<=n/2){
            return true;
        }
        left += gsize;
    }

    assert(left==n-1);

    return false;
}


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=true;
    if(sub==3){
        balanced=balancedSlow(n, r, diameter, group);
    }
    if(sub==4){
        balanced=balanced4(n, r, diameter, group);
    }

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

Compilation message

towns.cpp: In function 'bool balancedSlow(int, int, int, std::map<int, std::vector<int> >&)':
towns.cpp:34:29: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   34 |             cntleft+=g.size();
      |                             ^
towns.cpp: In function 'bool balanced4(int, int, int, std::map<int, std::vector<int> >&)':
towns.cpp:87:28: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   87 |             left += g.size();
      |                            ^
towns.cpp:91:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   91 |         int gsize=g.size();
      |                   ~~~~~~^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 9 ms 356 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 12 ms 348 KB Output is correct
5 Correct 12 ms 352 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 304 KB Output is correct
2 Correct 10 ms 340 KB Output is correct
3 Correct 12 ms 348 KB Output is correct
4 Correct 12 ms 340 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 340 KB Output is correct
2 Correct 13 ms 352 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 12 ms 340 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 340 KB Output is correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 39.0

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