Submission #1304902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304902		andrei_iorgulescu	Towns (IOI15_towns)	C++20	100 / 100	10 ms	1852 KiB

towns

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

using namespace std;

int inf = 1e9;

int dA[115], dB[115], n;
int l[115], dep[115];

bool eq(int i, int j)
{
    if (getDistance(i, j) == dep[i] + dep[j])
        return false;
    return true;
}

bool check(vector<int> v)
{
    if ((int)v.size() <= n / 2)
        return true;
    vector<int> coef(n);
    vector<pair<int, int>> cr;
    for (auto i : v)
        coef[i] = 1;
    for (auto i : v)
    {
        if (cr.empty())
            cr.push_back({i, 1});
        else
        {
            int x = cr.back().first, y = cr.back().second;
            cr.pop_back();
            if (eq(x, i))
            {
                y++;
                coef[x]++;
                coef[i] = 0;
                cr.push_back({x, y});
            }
            else
            {
                y--;
                if (y != 0)
                    cr.push_back({x, y});
            }
        }
    }
    ///gg de ce e vector xd
    if (cr.empty())
        return true;
    int x = cr[0].first;
    int fre = 0;
    for (auto i : v)
    {
        if (coef[i] != 0)
        {
            if (eq(i, x))
                fre += coef[i];
        }
    }
    if (fre <= n / 2)
        return true;
    return false;
}

int hubDistance(int N, int sub)
{
	int A = 0, B = 0, C = 0, diam;
	n = N;
	dA[0] = 0;
	for (int i = 1; i < n; i++)
    {
        dA[i] = getDistance(0, i);
        if (dA[i] > dA[B])
            B = i;
    }
    for (int i = 0; i < n; i++)
    {
        if (i == 0)
            dB[i] = dA[B];
        else if (i == B)
            dB[i] = 0;
        else
            dB[i] = getDistance(B, i);
        if (dB[i] > dB[C])
            C = i;
    }
    diam = dB[C];
    for (int i = 0; i < n; i++)
        l[i] = dep[i] = 0;
    dep[A] = (dA[C] + dA[B] - diam) / 2;
    l[A] = dA[B] - dep[A];
    vector<int> L, M, R;
    set<int> ls;
    ls.insert(l[A]);
    map<int, int> oo;
    map<int, vector<int>> vv;
    for (int i = 0; i < n; i++)
    {
        int df = dB[i] - dA[i];
        if (df > l[A] - dep[A])
            M.push_back(i), oo[l[A]]++;
        else if (df == l[A] - dep[A])
            L.push_back(i), oo[inf]++;
        else
        {
            int delt = (l[A] - dep[A] - df) / 2;
            R.push_back(i);
            l[i] = l[A] - delt;
            ls.insert(l[i]);
            oo[l[i]]++;
            vv[l[i]].push_back(i);
            dep[i] = dB[i] - l[i];
        }
    }
    int difmin = 1e9;
    for (auto it : ls)
        difmin = min(difmin, max(it, diam - it));
    vector<int> cand;
    for (auto it : ls)
        if (max(it, diam - it) == difmin)
            cand.push_back(it);
    int RR = difmin;
    if (sub <= 2)
        return RR;
    bool found = false;
    for (auto it : cand)
    {
        if (it != l[A])
        {
            int st = 0, eu = 0, dr = 0;
            for (auto itt : oo)
            {
                if (itt.first < it)
                    dr += itt.second;
                else if (itt.first == it)
                    eu += itt.second;
                else
                    st += itt.second;
            }
            if (st > n / 2 or dr > n / 2)
                continue;
            if (eu <= n / 2)
            {
                found = true;
                break;
            }
            found |= check(vv[it]);
        }
        else
        {
            int dr = 0;
            for (auto itt : oo)
                if (itt.first < it)
                    dr += itt.second;
            if (dr > n / 2)
                continue;
            vector<int> vec;
            for (auto el : M)
            {
                vec.push_back(el);
                dep[el] = dB[el] - l[A];
            }
            for (auto el : L)
            {
                vec.push_back(el);
                dep[el] = dB[el] - l[A];
            }
            found |= check(vec);
        }
    }
    if (!found)
        RR = -RR;
    return RR;
}

///de cand nu a mai trebuit sa gandesc ca sa rezolv o problema...

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