Submission #287291

#	Time	Username	Problem	Language	Result	Execution time	Memory
287291		evpipis	Towns (IOI15_towns)	C++11	49 / 100	22 ms	1024 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;
    for (int i = 0; i < ball.size(); i++){
        int cur = ball[i];
        if (!stck.empty() && !check(stck.back(), cur))
            stck.pop_back();
        else
            stck.pb(cur);
    }

    if (stck.empty())
        return true;

    int cnt = 0;
    for (auto cur: ball)
        if (check(cur, 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:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i = 0; i < ball.size(); i++){
      |                     ~~^~~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:103:34: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  103 |             lef += (*it).se.size(), it++;
      |                                  ^
towns.cpp:105:31: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  105 |         int sz = (*it).se.size();
      |                  ~~~~~~~~~~~~~^~
towns.cpp:88:28: warning: unused parameter 'sub' [-Wunused-parameter]
   88 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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