Submission #778739

#	Time	Username	Problem	Language	Result	Execution time	Memory
778739		danikoynov	Towns (IOI15_towns)	C++14	48 / 100	16 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]));
}

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

    par[u] = v;
    rnk[v] += rnk[u];
}
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)
    {
        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;
                    }
                    ///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)
                    {
                        if (rnk[find_leader(v)] > N / 2)
                            tf = false;
                    }

                    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 'int getLocalDistance(int, int)':
towns.cpp:13:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   13 |     if (table[v][u] != 0)
      |     ^~
towns.cpp:15:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   15 |         table[v][u] = table[u][v] = getDistance(v, u);
      |         ^~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:117:44: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  117 |             int from_right = N - from_left - it.second.size();
      |                              ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
towns.cpp:123:30: warning: declaration of 'v' shadows a previous local [-Wshadow]
  123 |                     for (int v : st)
      |                              ^
towns.cpp:41:9: note: shadowed declaration is here
   41 |     int v = 0, u = -1, best = 0;
      |         ^
towns.cpp:129:30: warning: declaration of 'v' shadows a previous local [-Wshadow]
  129 |                     for (int v : st)
      |                              ^
towns.cpp:41:9: note: shadowed declaration is here
   41 |     int v = 0, u = -1, best = 0;
      |         ^
towns.cpp:130:34: warning: declaration of 'u' shadows a previous local [-Wshadow]
  130 |                         for (int u : st)
      |                                  ^
towns.cpp:41:16: note: shadowed declaration is here
   41 |     int v = 0, u = -1, best = 0;
      |                ^
towns.cpp:141:30: warning: declaration of 'v' shadows a previous local [-Wshadow]
  141 |                     for (int v : st)
      |                              ^
towns.cpp:41:9: note: shadowed declaration is here
   41 |     int v = 0, u = -1, best = 0;
      |         ^
towns.cpp:151:41: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  151 |             from_left += it.second.size();
      |                                         ^

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