Submission #380281

#	Time	Username	Problem	Language	Result	Execution time	Memory
380281		idk321	Towns (IOI15_towns)	C++11	26 / 100	46 ms	1004 KiB

towns

#include "towns.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, cur;

const int N = 300;
int dist[N][N];
const int M = 1000000000;

vector<int> nodes;
vector<array<int, 2>> adj[N];

void solve()
{

    if (nodes.size() == 1) return;

    int toDel = -1;
    for (int i = 0; i < nodes.size(); i++)
    {

        for (int j = 0; j < nodes.size(); j++)
        {
            if (i == j) continue;

            bool ok = true;
            for (int k = 0; k < nodes.size(); k++)
            {
                if (k == i || k == j) continue;

                if (dist[nodes[k]][nodes[i]] - dist[nodes[k]][nodes[j]] != dist[nodes[i]][nodes[j]])
                {
                    ok = false;
                    break;
                }

            }

            if (ok)
            {
                adj[nodes[i]].push_back({nodes[j], dist[nodes[i]][nodes[j]]});
                adj[nodes[j]].push_back({nodes[i], dist[nodes[i]][nodes[j]]});
                toDel = nodes[i];
                break;
            }
        }
        if (toDel != -1) break;
    }

    if (toDel != -1)
    {
        for (int i = 0; i < nodes.size(); i++)
        {
            if (nodes[i] == toDel)
            {
                nodes.erase(nodes.begin() + i);
                break;
            }
        }

        solve();
        return;
    }


    array<int, 2> ar = {-1, -1};
    for (int i = 0; i < nodes.size(); i++)
    {
        for (int j = i + 1; j < nodes.size(); j++)
        {
            bool ok = true;
            int ci = M;
            for (int k = 0; k < nodes.size(); k++)
            {

                if (k == i || k == j) continue;
                if (ci == M)
                {
                    ci = dist[nodes[j]][nodes[k]] - dist[nodes[i]][nodes[k]];
                } else
                {
                    if (ci != dist[nodes[j]][nodes[k]] - dist[nodes[i]][nodes[k]])
                    {
                        ok = false;
                        break;
                    }
                }
            }

            if (ok)
            {
                ar[0] = nodes[i];
                ar[1] = nodes[j];

                adj[nodes[i]].push_back({cur, (dist[nodes[i]][nodes[j]] - ci) / 2});
                adj[cur].push_back({nodes[i], (dist[nodes[i]][nodes[j]] - ci) / 2});
                adj[nodes[j]].push_back({cur, (dist[nodes[i]][nodes[j]] + ci) / 2});
                for (int l = 0; l < N; l++)
                {
                    if (dist[nodes[i]][l] != 0)
                    {

                        dist[cur][l] = dist[nodes[i]][l] - (dist[nodes[i]][nodes[j]] - ci) / 2;
                        dist[l][cur] = dist[cur][l];
                    }
                }
                adj[cur].push_back({nodes[j], (dist[nodes[i]][nodes[j]] + ci) / 2});
                nodes.push_back(cur);
                cur++;
                break;
            }
        }

        if (ar[0] != -1) break;
    }



    for (int i = 0; i < nodes.size(); i++)
    {
        if (nodes[i] == ar[0])
        {
            nodes.erase(nodes.begin() + i);
        }
    }
    for (int i = 0; i < nodes.size(); i++)
    {
        if (nodes[i] == ar[1])
        {
            nodes.erase(nodes.begin() + i);
        }
    }



    solve();
}

int getMaxDist(int node, int par)
{

    int res = 0;

    for (auto next : adj[node])
    {
        if (next[0] == par) continue;
        res = max(res, getMaxDist(next[0], node) + next[1]);
    }


    return res;
}

int sz[N];

void getSz(int node,  int par)
{
    sz[node] = 0;
    if (adj[node].size() == 1) sz[node] = 1;
    for (auto next : adj[node])
    {
        if (next[0] == par) continue;
        getSz(next[0], node);
        sz[node] += sz[next[0]];
    }
}
bool isGood(int node)
{

    for (auto next : adj[node])
    {

        if (sz[next[0]] > n / 2) return false;
    }

    return true;
}

int hubDistance(int N, int sub) {

    n = N;
    cur = n;

    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            dist[i][j] = getDistance(i, j);
            dist[j][i] = dist[i][j];
        }
    }

    for (int i = 0; i < n; i++) nodes.push_back(i);

    solve();

    bool good = false;
    int r = M;
    for (int i = n; i < cur; i++)
    {
        r = min(r, getMaxDist(i, -1));
    }

    for (int i = n; i < cur; i++)
    {
        if (getMaxDist(i, -1) == r)
        {
            getSz(i, -1);
            good = good || isGood(i);
        }
    }


    nodes.clear();
    for (int i = 0; i < cur; i++) adj[i].clear();
    if (!good) r *= -1;
	return r;
}

Compilation message (stderr)

towns.cpp: In function 'void solve()':
towns.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < nodes.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
towns.cpp:25:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (int j = 0; j < nodes.size(); j++)
      |                         ~~^~~~~~~~~~~~~~
towns.cpp:30:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             for (int k = 0; k < nodes.size(); k++)
      |                             ~~^~~~~~~~~~~~~~
towns.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int i = 0; i < nodes.size(); i++)
      |                         ~~^~~~~~~~~~~~~~
towns.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i = 0; i < nodes.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
towns.cpp:72:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int j = i + 1; j < nodes.size(); j++)
      |                             ~~^~~~~~~~~~~~~~
towns.cpp:76:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             for (int k = 0; k < nodes.size(); k++)
      |                             ~~^~~~~~~~~~~~~~
towns.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for (int i = 0; i < nodes.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
towns.cpp:129:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for (int i = 0; i < nodes.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:182:31: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  182 | int hubDistance(int N, int sub) {
      |                               ^
towns.cpp:9:11: note: shadowed declaration is here
    9 | const int N = 300;
      |           ^
towns.cpp:182:28: warning: unused parameter 'sub' [-Wunused-parameter]
  182 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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