Submission #287283

#	Time	Username	Problem	Language	Result	Execution time	Memory
287283		evpipis	Towns (IOI15_towns)	C++11	35 / 100	35 ms	432 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);
    }
}

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 (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 'int hubDistance(int, int)':
towns.cpp:79:34: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   79 |             lef += (*it).se.size(), it++;
      |                                  ^
towns.cpp:81:31: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   81 |         int sz = (*it).se.size();
      |                  ~~~~~~~~~~~~~^~
towns.cpp:64:28: warning: unused parameter 'sub' [-Wunused-parameter]
   64 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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