Submission #778725

#	Time	Username	Problem	Language	Result	Execution time	Memory
778725		danikoynov	Towns (IOI15_towns)	C++14	35 / 100	16 ms	352 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 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)
{
    int v = 0, u = -1, best = 0;
    for (int i = 1; i < N; i ++)
    {
        int d = getDistance(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 = getDistance(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 = getDistance(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 = getDistance(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)
        {
            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;
                    }
                    for (int v : st)
                        for (int u : st)
                    {
                        if (v == u)
                            continue;
                        int part = (dist[v] + dist[u] - getDistance(v, u)) / 2;
                        if (part != 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 = getDistance(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 hubDistance(int, int)':
towns.cpp:102:44: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  102 |             int from_right = N - from_left - it.second.size();
      |                              ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
towns.cpp:108:30: warning: declaration of 'v' shadows a previous local [-Wshadow]
  108 |                     for (int v : st)
      |                              ^
towns.cpp:28:9: note: shadowed declaration is here
   28 |     int v = 0, u = -1, best = 0;
      |         ^
towns.cpp:113:30: warning: declaration of 'v' shadows a previous local [-Wshadow]
  113 |                     for (int v : st)
      |                              ^
towns.cpp:28:9: note: shadowed declaration is here
   28 |     int v = 0, u = -1, best = 0;
      |         ^
towns.cpp:114:34: warning: declaration of 'u' shadows a previous local [-Wshadow]
  114 |                         for (int u : st)
      |                                  ^
towns.cpp:28:16: note: shadowed declaration is here
   28 |     int v = 0, u = -1, best = 0;
      |                ^
towns.cpp:124:30: warning: declaration of 'v' shadows a previous local [-Wshadow]
  124 |                     for (int v : st)
      |                              ^
towns.cpp:28:9: note: shadowed declaration is here
   28 |     int v = 0, u = -1, best = 0;
      |         ^
towns.cpp:133:41: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  133 |             from_left += it.second.size();
      |                                         ^

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