Submission #778831

#	Time	Username	Problem	Language	Result	Execution time	Memory
778831		danikoynov	Towns (IOI15_towns)	C++14	61 / 100	13 ms	900 KiB

towns

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

using namespace std;
const int maxn = 120;
int dist[maxn];
int par[maxn], rnk[maxn], path[maxn];

int table[maxn][maxn];

int getLocalDistance(int v, int u)
{
    if (table[v][u] != 0)
        return table[v][u];
    table[v][u] = table[u][v] = getDistance(v, u);
    return table[v][u];
}
int find_leader(int v)
{
    if (par[v] == v)
        return v;
    return (par[v] = find_leader(par[v]));
}

bool unite(int v, int u)
{
    v = find_leader(v);
    u = find_leader(u);
    if (v == u)
        return false;

    par[u] = v;
    rnk[v] += rnk[u];
    return true;
}

vector < int > get_biggest(vector < int > st, int mst)
{
    cout << "biggest " << " " << st.size() << " " << mst << endl;
    for (int v : st)
        cout << rnk[find_leader(v)] << " ";
    cout << endl;
    if (st.size() == 1)
        return st;
    vector < int > res;
    for (int v : st)
    {
        if (res.empty())
            res.push_back(v);
        else
        {
            int a = find_leader(res.back()), b = find_leader(v);
            int part = (dist[a] + dist[b] - getLocalDistance(a, b)) / 2;
            if (part != mst)
                unite(a, b);
            else
                res.push_back(b);
        }
    }

    while(res.size() > 1)
    {
        int a = find_leader(res[0]), b = find_leader(res.back());
        int part = (dist[a] + dist[b] - getLocalDistance(a, b)) / 2;
        if (part != mst)
            unite(a, b), res.pop_back();
        else
            break;
    }
    vector < int > odd, even;
    int sz1 = 0, sz2 = 0;
    ///cout << "fine" << endl;
    for (int i = 0; i < res.size(); i ++)
    {
        //cout << find_leader(res[i]) << " --- " << res[i] << endl;
        ///if (i == 1)
           // exit(0);
        if (i % 2 ==0)
            even.push_back(res[i]), sz1 += rnk[find_leader(res[i])];
        else
            odd.push_back(res[i]), sz2 += rnk[find_leader(res[i])];
    }

    if (sz1 > sz2)
        return get_biggest(even, mst);
    else
        return get_biggest(odd, mst);
}
int hubDistance(int N, int sub)
{
    ///cout << "hub " << N << " " << sub << endl;
    for (int i = 0; i < N; i ++)
        for (int j = 0; j < N; j ++)
            table[i][j] = 0;
    int v = 0, u = -1, best = 0;
    for (int i = 1; i < N; i ++)
    {
        int d = getLocalDistance(i, 0);
        if (u == -1 || d > best)
        {
            best = d;
            u = i;
        }
    }
    dist[0] = best;
    for (int i = 1; i < N; i ++)
    {
        if (i != u)
        {
            int d = getLocalDistance(i, u);
            dist[i] = d;
            if (d > best)
            {
                best = d;
                v = i;
            }
        }
    }
    if (sub == 4)
    {
        map < int, int > marked;
        int ans = 1e9;
        for (int i = 0; i < N; i ++)
        {
            if (i == v || i == u)
                continue;
            int df = getLocalDistance(v, i), tf = dist[i];
            int diff = abs(df - tf);
            int lf = (best - diff) / 2 + diff, rf = (best - diff) / 2;
            if (df < tf)
                swap(lf, rf);
            marked[lf] ++;
            ans = min(ans, (best - diff) / 2 + diff);
        }
        int from_left = 1;
        for (auto it : marked)
        {
            int from_right = N - from_left - it.second;
            if (max(it.first, best - it.first) == ans)
            {
                if (max(from_right, max(it.second, from_left)) <= N / 2)
                    return +ans;
            }
            from_left += it.second;
        }
        return -ans;
    }
    else if (sub == 3 || sub == 5)
    {
        map < int, vector < int > > marked;
        int ans = 1e9;
        for (int i = 0; i < N; i ++)
        {
            if (i == v || i == u)
                continue;
            int df = getLocalDistance(v, i), tf = dist[i];
            path[i] = v;
            int diff = abs(df - tf);
            int lf = (best - diff) / 2 + diff, rf = (best - diff) / 2;
            if (df < tf)
                swap(lf, rf);
            marked[lf].push_back(i);
            ans = min(ans, (best - diff) / 2 + diff);
        }

        int from_left = 1;
        for (auto it : marked)
        {
            ///cout << it.first << " : " << ans << endl;
            int from_right = N - from_left - it.second.size();
            if (max(it.first, best - it.first) == ans)
            {
                if (from_left <= N / 2 && from_right <= N / 2)
                {
                    vector < int > st = it.second;
                    for (int v : st)
                    {
                        par[v] = v;
                        rnk[v] = 1;
                    }
                    int maj = -1, cnt = 0;
                    for (int v : st)
                    {
                        if (cnt == 0)
                        {
                            ///cout << "make majorant " << v << endl;
                            maj = v;
                            cnt ++;
                        }
                        else
                        {

                            int part = (dist[maj] + dist[v] - getLocalDistance(maj, v)) / 2;
                            ///cout << "here " << maj << " " << cnt << " " << part << " " << best - it.first << endl;
                            if (part != best - it.first)
                                cnt ++, unite(maj, v);
                            else
                                cnt --;
                        }
                    }

                    if (cnt == 0)
                        return ans;
                                    for (int v : st)
                    {
                        if (v == maj)
                            continue;
                        int part = (dist[maj] + dist[v] - getLocalDistance(maj, v)) / 2;
                        if (part != best - it.first)
                            unite(maj, v);
                    }

                    if (rnk[find_leader(maj)] <= N / 2)
                        return ans;


                    ///cout << "HERE " << N << " " << st.size() << endl;
                    /**for (int v : st)
                        for (int u : st)
                    {

                        if (v >= u)
                            continue;
                        int part = (dist[v] + dist[u] - getLocalDistance(v, u)) / 2;
                        if (part != best - it.first)
                            unite(v, u);
                    }

                    bool tf = true;
                    for (int v : st)
                    {
                        cout << rnk[find_leader(v)] << " ";
                        if (rnk[find_leader(v)] > N / 2)
                            tf = false;
                    }
                    cout << endl;

                    if (tf)
                        return ans;*/
                }
            }
            from_left += it.second.size();
        }

        return -ans;
    }
    else
    {

        int ans = 1e9;
        for (int i = 0; i < N; i ++)
        {
            if (i == v || i == u)
                continue;
            int df = getLocalDistance(v, i), tf = dist[i];
            int diff = abs(df - tf);
            ans = min(ans, (best - diff) / 2 + diff);
        }

        return ans;
    }
}

Compilation message (stderr)

towns.cpp: In function 'std::vector<int> get_biggest(std::vector<int>, int)':
towns.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i = 0; i < res.size(); i ++)
      |                     ~~^~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:170:44: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  170 |             int from_right = N - from_left - it.second.size();
      |                              ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
towns.cpp:176:30: warning: declaration of 'v' shadows a previous local [-Wshadow]
  176 |                     for (int v : st)
      |                              ^
towns.cpp:95:9: note: shadowed declaration is here
   95 |     int v = 0, u = -1, best = 0;
      |         ^
towns.cpp:182:30: warning: declaration of 'v' shadows a previous local [-Wshadow]
  182 |                     for (int v : st)
      |                              ^
towns.cpp:95:9: note: shadowed declaration is here
   95 |     int v = 0, u = -1, best = 0;
      |         ^
towns.cpp:204:46: warning: declaration of 'v' shadows a previous local [-Wshadow]
  204 |                                     for (int v : st)
      |                                              ^
towns.cpp:95:9: note: shadowed declaration is here
   95 |     int v = 0, u = -1, best = 0;
      |         ^
towns.cpp:242:41: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  242 |             from_left += it.second.size();
      |                                         ^

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