Submission #165802

#	Time	Username	Problem	Language	Result	Execution time	Memory
165802		tri	Towns (IOI15_towns)	C++14	100 / 100	22 ms	1144 KiB

towns

#include <bits/stdc++.h>
#include "towns.h"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = true;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;

int N;

vi fDists(int x) {
    vi dists(N);
    for (int i = 0; i < N; i++) {
        if (x == i || i == 0) { // dist to 0 = dist from 0
            dists[i] = 0;
        } else {
            dists[i] = getDistance(x, i);
        }
    }
    return dists;
}

vector<pair<int, vi>> centV;
vi x;

bool sameTree(int a, int b) {
    return getDistance(a, b) < x[a] + x[b];
}

bool checkSplit(vi &list) {
    vi record;

    int cur = -1;
    int cnt = 0;

    for (int i = 0; i < list.size(); i++) {
        if (cnt == 0) {
            record.pb(-1);
            cur = list[i];
            cnt = 1;
        } else {
            if (sameTree(cur, list[i])) {
                record.pb(cur);
                cnt++;
            } else {
                record.pb(-1);
                cnt--;
            }
        }
    }

    int tCnt = 0;

    vi saved(N);

    for (int i = 0; i < list.size(); i++) {
        if (record[i] != -1) {
            tCnt += saved[record[i]];
        } else {
            int res = sameTree(list[i], cur);
            saved[list[i]] = res;
            tCnt += res;
        }
    }
    return tCnt <= N / 2;
}


int hubDistance(int iN, int sub) {
    centV.clear();
    x.clear();
    N = iN;
    vi dists0 = fDists(0);

    int d1 = -1;
    for (int i = 0; i < N; i++) {
        if (d1 == -1 || dists0[i] > dists0[d1]) {
            d1 = i;
        }
    }

    vi distsD1 = fDists(d1);
    distsD1[0] = dists0[d1];

    int d2 = -1;
    for (int i = 0; i < N; i++) {
        if (d2 == -1 || distsD1[i] > distsD1[d2]) {
            d2 = i;
        }
    }

    int diameter = distsD1[d2];

    int pd = distsD1[0] - (distsD1[0] + dists0[d2] - diameter) / 2;

    map<int, vi> cent;

    for (int i = 0; i < N; i++) {
        int cX = (dists0[i] + distsD1[i] - dists0[d1]) / 2;
        x.pb(cX);
        int y = distsD1[i] - cX;

        if (y < pd) {
            cent[y].pb(i);
        }
        if (y == pd) {
            cent[pd].pb(i);
        }
        if(y > pd){
            cent[pd].pb(i);
            x[i] = distsD1[i] - pd;
        }
    }

    for (auto &dv : cent) {
        centV.pb(dv);
    }

    int R = 1e9;

    for (auto &dv : centV) {
        int cD = dv.f;
        if (R > max(cD, diameter - cD)) {
            R = max(cD, diameter - cD);
        }
    }

    vi hubs;

    for (int i = 0; i < centV.size(); i++) {
        int cD = centV[i].f;
        if (R == max(cD, diameter - cD)) {
            hubs.pb(i);
        }
    }

    vi bef(centV.size()), aft(centV.size());

    bef[0] = 0;
    for (int i = 1; i < centV.size(); i++) {
        bef[i] = bef[i - 1] + centV[i - 1].s.size();
    }

    aft[centV.size() - 1] = 0;
    for (int i = centV.size() - 2; i >= 0; i--) {
        aft[i] = aft[i + 1] + centV[i + 1].s.size();
    }

    bool bal = false;
    for (int hub :hubs) {
        assert(bef[hub] + aft[hub] + centV[hub].s.size() == N);
        if (bef[hub] <= N / 2 && aft[hub] <= N / 2) {
            if (centV[hub].s.size() <= N / 2) {
                bal = true;
            } else if (!bal) {
                // does splitting into different subtrees make it <= N/2 ?
                bal |= checkSplit(centV[hub].s);
            }
        }
    }

    if (bal) {
        return R;
    } else {
        return -R;
    }
}

Compilation message (stderr)

towns.cpp: In function 'bool checkSplit(vi&)':
towns.cpp:105:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < list.size(); i++) {
                     ~~^~~~~~~~~~~~~
towns.cpp:125:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < list.size(); i++) {
                     ~~^~~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:199:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < centV.size(); i++) {
                     ~~^~~~~~~~~~~~~~
towns.cpp:209:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < centV.size(); i++) {
                     ~~^~~~~~~~~~~~~~
towns.cpp:210:29: warning: conversion to '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
         bef[i] = bef[i - 1] + centV[i - 1].s.size();
towns.cpp:214:31: warning: conversion to 'int' from 'std::vector<std::pair<int, std::vector<int> > >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
     for (int i = centV.size() - 2; i >= 0; i--) {
                  ~~~~~~~~~~~~~^~~
towns.cpp:215:29: warning: conversion to '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
         aft[i] = aft[i + 1] + centV[i + 1].s.size();
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from towns.cpp:1:
towns.cpp:220:58: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         assert(bef[hub] + aft[hub] + centV[hub].s.size() == N);
towns.cpp:222:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (centV[hub].s.size() <= N / 2) {
                 ~~~~~~~~~~~~~~~~~~~~^~~~~~~~
towns.cpp:138:29: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int iN, 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