Submission #287269

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

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;
        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;

    fix_graph();
    find_hubs(R, hubs);

	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:56:28: warning: unused parameter 'sub' [-Wunused-parameter]
   56 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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