Submission #287305

#	Time	Username	Problem	Language	Result	Execution time	Memory
287305		evpipis	Towns (IOI15_towns)	C++11	100 / 100	31 ms	896 KiB

towns

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

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;

const int len = 115;
int n, s, a, b, dep[len];
map<ii, int> mym;
map<int, vector<int> > adj;

int ask(int a, int b){
    if (a > b)
        swap(a, b);
    if (mym.count(mp(a, b)))
        return mym[mp(a, b)];
    return mym[mp(a, b)] = getDistance(a, b);
}

void fix_graph(){
    s = 0, a = 0, b = 0;
    for (int i = 0; i < n; i++)
        if (ask(s, i) > ask(s, a))
            a = i;
    for (int i = 0; i < n; i++)
        if (ask(a, i) > ask(a, b))
            b = i;

    adj.clear();
    for (int i = 0; i < n; i++){
        int pos = (ask(a, i)+ask(a, s)-ask(s, i))/2;
        adj[pos].pb(i);

        dep[i] = (ask(a, i)+ask(s, i)-ask(a, s))/2;

        //printf("i = %d, dep = %d, pos = %d\n", i, dep[i], pos);
    }

    //printf("graph fixed\n");
    //printf("s = %d, a = %d, b = %d\n", s, a, b);
}

void find_hubs(int &R, vector<int> &hubs){
    int diam = ask(a, b);

    R = diam;
    hubs.clear();
    for (auto &it: adj){
        int pos = it.fi;

        //printf("pos = %d\n", pos);
        //printf("mx = %d\n", max(pos, diam-pos));
        if (max(pos, diam-pos) < R)
            hubs.clear(), hubs.pb(pos), R = max(pos, diam-pos);
        else if (max(pos, diam-pos) == R)
            hubs.pb(pos);
    }
}

bool check(int a, int b){
    return (ask(a, b) < dep[a]+dep[b]);
}

bool check_cent(vector<int> ball){
    vector<int> stck;
    vector<vector<ii> > cons;
    for (int i = 0; i < ball.size(); i++){
        int cur = ball[i];
        if (stck.empty())
            cons.pb(vector<ii>(0));

        if (!stck.empty() && !check(stck.back(), cur))
            cons.back().pb(mp(stck.back(), cur)), stck.pop_back();
        else
            stck.pb(cur);
    }

    if (stck.empty())
        return true;

    /*printf("now cons:\n");
    for (int x = 0; x < cons.size(); x++){
        printf("x = %d\n", x);
        for (int y = 0; y < cons[x].size(); y++)
            printf("(%d, %d) ", cons[x][y].fi, cons[x][y].se);
        printf("\n");
    }*/

    int cnt = stck.size();
    for (int i = 0; i < cons.size(); i++){
        if (cons[i].empty()) continue;

        if (check(cons[i][0].fi, stck.back())){
            cnt += cons[i].size();
            continue;
        }

        for (int j = 0; j < cons[i].size(); j++)
            if (check(cons[i][j].se, stck.back()))
                cnt++;
    }

    return (cnt <= n/2);
}

int hubDistance(int N, int sub) {
    mym.clear(), n = N;

    vector<int> hubs;
    int R, balanced = 0;

    fix_graph();

    find_hubs(R, hubs);

    auto it = adj.begin();
    int lef = 0;
    for (auto pos: hubs){
        //printf("pos = %d\n", pos);
        while ((*it).fi < pos)
            lef += (*it).se.size(), it++;

        int sz = (*it).se.size();
        if (lef <= n/2 && sz <= n/2 && (n-lef-sz) <= n/2)
            balanced = 1;
        //printf("sz = %d\n", sz);
        if (sz > n/2 && check_cent((*it).se))
            balanced = 1;
    }

    if (balanced)
        return R;
    else
        return -R;
}

Compilation message (stderr)

towns.cpp: In function 'int ask(int, int)':
towns.cpp:16:21: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   16 | int ask(int a, int b){
      |                     ^
towns.cpp:12:14: note: shadowed declaration is here
   12 | int n, s, a, b, dep[len];
      |              ^
towns.cpp:16:21: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   16 | int ask(int a, int b){
      |                     ^
towns.cpp:12:11: note: shadowed declaration is here
   12 | int n, s, a, b, dep[len];
      |           ^
towns.cpp: In function 'bool check(int, int)':
towns.cpp:64:24: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   64 | bool check(int a, int b){
      |                        ^
towns.cpp:12:14: note: shadowed declaration is here
   12 | int n, s, a, b, dep[len];
      |              ^
towns.cpp:64:24: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   64 | bool check(int a, int b){
      |                        ^
towns.cpp:12:11: note: shadowed declaration is here
   12 | int n, s, a, b, dep[len];
      |           ^
towns.cpp: In function 'bool check_cent(std::vector<int>)':
towns.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 0; i < ball.size(); i++){
      |                     ~~^~~~~~~~~~~~~
towns.cpp:93:24: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   93 |     int cnt = stck.size();
      |               ~~~~~~~~~^~
towns.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = 0; i < cons.size(); i++){
      |                     ~~^~~~~~~~~~~~~
towns.cpp:98:33: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   98 |             cnt += cons[i].size();
      |                                 ^
towns.cpp:102:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for (int j = 0; j < cons[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:125:34: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  125 |             lef += (*it).se.size(), it++;
      |                                  ^
towns.cpp:127:31: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  127 |         int sz = (*it).se.size();
      |                  ~~~~~~~~~~~~~^~
towns.cpp:110:28: warning: unused parameter 'sub' [-Wunused-parameter]
  110 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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