Submission #288584

#	Time	Username	Problem	Language	Result	Execution time	Memory
288584		Kastanda	Towns (IOI15_towns)	C++11	100 / 100	26 ms	640 KiB

towns

// M
#include<bits/stdc++.h>
#include "towns.h"
using namespace std;
const int N = 119;
int n, sub, D[N][N], A[N], F[N], P[N];
vector < int > Fail[N];
inline int Dist(int a, int b)
{
        if (a == b)
                return 0;
        if (D[a][b] != -1)
                return D[a][b];
        D[a][b] = D[b][a] = getDistance(a, b);
        return D[a][b];
}
int Find(int v)
{
        return (P[v] < 0 ? v : (P[v] = Find(P[v])));
}
inline void Merge(int v, int u)
{
        v = Find(v);
        u = Find(u);
        if (v == u)
                return ;
        for (int a : Fail[u])
                Fail[v].push_back(a);
        Fail[u].clear();
        P[v] += P[u];
        P[u] = v;
}
inline int Oracle(int v, int u)
{
        v = Find(v);
        u = Find(u);
        if (v == u)
                return 1;
        for (int a : Fail[v])
                if (Find(a) == u)
                        return 0;
        for (int a : Fail[u])
                if (Find(a) == v)
                        return 0;
        return -1;
}
inline bool SameComp(int v, int u)
{
        int w = Oracle(v, u);
        if (w != -1)
                return w;

        assert(Find(v) != Find(u));
        if (Dist(v, u) < A[v] + A[u])
        {
                Merge(v, u);
                return 1;
        }
        else
        {
                Fail[Find(v)].push_back(Find(u));
                Fail[Find(u)].push_back(Find(v));
                return 0;
        }
}
int shdbe = -1;
void Solve(vector < int > vec)
{
        int odd = -1;
        if ((int)vec.size() & 1)
                odd = vec.back(), vec.pop_back();
        vector < int > sames;
        for (int i = 1; i < (int)vec.size(); i += 2)
                if (SameComp(vec[i - 1], vec[i]))
                        sames.push_back(vec[i]);
        if ((int)sames.size() == 1)
        {
                shdbe = sames[0];
                return ;
        }
        if ((int)sames.size() > 1)
                Solve(sames);

        if (shdbe != -1)
                return ;

        if (odd != -1)
        {
                shdbe = odd;
                return ;
        }
        return ;
}
inline bool isOkay(vector < int > vec, int szlim)
{
        memset(P, -1, sizeof(P));
        for (int i = 0; i < n; i ++)
                Fail[i].clear();
        shdbe = -1;
        Solve(vec);
        if (shdbe == -1)
                return 1;
        int cnt = 0;
        for (int v : vec)
                if (SameComp(v, shdbe))
                {
                        cnt ++;
                        if (cnt > szlim)
                                return 0;
                }
        return 1;
}
int hubDistance(int _n, int _sub)
{
        n = _n; sub = _sub;
        memset(D, -1, sizeof(D));

        int diam1 = 0;
        for (int i = 1; i < n; i ++)
                if (Dist(0, i) > Dist(0, diam1))
                        diam1 = i;
        int diam2 = 0;
        for (int i = 0; i < n; i ++)
                if (Dist(diam1, i) > Dist(diam1, diam2))
                        diam2 = i;

        // Corner cases : diam2 = 0 ?
        F[0] = (Dist(0, diam1) - Dist(0, diam2) + Dist(diam1, diam2)) / 2;
        A[0] = Dist(0, diam1) - F[0];

        int Rad = INT_MAX;
        vector < int > Centre;
        for (int i = 1; i < n; i ++)
        {
                int df = Dist(i, diam1) - Dist(i, 0) + Dist(diam1, 0);
                df /= 2;
                if (df >= F[0])
                        df = F[0];
                A[i] = Dist(i, diam1) - df;
                F[i] = df;

                if (Rad > max(df, Dist(diam1, diam2) - df))
                        Rad = max(df, Dist(diam1, diam2) - df), Centre.clear();
                if (Rad == max(df, Dist(diam1, diam2) - df))
                        Centre.push_back(df);
        }
        sort(Centre.begin(), Centre.end());
        Centre.resize(unique(Centre.begin(), Centre.end()) - Centre.begin());
        assert((int)Centre.size() <= 2);

        if (sub <= 2)
                return Rad;

        int szlim = n / 2, cc = 0;
        for (int centroid : Centre)
        {
                vector < int > vec;
                int cle = 0, cri = 0, cmd = 0;
                for (int i = 0; i < n; i ++)
                {
                        if (F[i] < centroid)
                                cle ++;
                        else if (F[i] > centroid)
                                cri ++;
                        else
                                cmd ++, vec.push_back(i);
                }
                if (cle > szlim || cri > szlim)
                        continue;
                if (cmd <= szlim)
                        return Rad;
                cc ++;
                assert(cc == 1);
                if (isOkay(vec, szlim))
                        return Rad;
        }
        return -Rad;
}

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