Submission #802388

#	Time	Username	Problem	Language	Result	Execution time	Memory
802388		caganyanmaz	Towns (IOI15_towns)	C++14	25 / 100	15 ms	352 KiB

towns

#include <bits/stdc++.h>
#define pb push_back
#include "towns.h"
using namespace std;


constexpr static int INF = 2e9;
constexpr static int MXSIZE = 110;

int n;

vector<int> ll, ml, mr, rr;
int ldist[MXSIZE];
int rdist[MXSIZE];

int r;

bool connected(int i, int j, int* dist)
{
        bool res = dist[i] + dist[j] > (getDistance(i, j) + r * 2);
        return res;
}

bitset<MXSIZE> visited;
vector<int> g[MXSIZE];
int dfs(int node)
{
        visited[node] = true;
        int sum = 1;
        for (int c : g[node])
                if (!visited[c])
                        sum += dfs(c);
        return sum;
}

bool check(const vector<int>& v, int* dist)
{
        for (int i = 0; i < v.size(); i++)
        {
                for (int j = i+1; j < v.size(); j++)
                {
                        if (connected(v[i], v[j], dist))
                        {
                                g[v[i]].pb(v[j]);
                                g[v[j]].pb(v[i]);
                        }
                }
        }
        int mxsize = 0;
        for (int i : v)
                if (!visited[i])
                        mxsize = max(mxsize, dfs(i));
        return mxsize <= (n/2);
}

int hubDistance(int N, int sub)
{
        n = N;
        int mxdist = 0;
        int j = 0;
        for (int i = 1; i < n; i++)
        {
                int val = getDistance(0, i);
                if (val > mxdist)
                {
                        j = i;
                        mxdist = val;
                }
        }
        int k = 0;
        ldist[0] = mxdist;
        for (int i = 1; i < n; i++)
        {
                if (i == j)
                        continue;
                int val = getDistance(i, j);
                ldist[i] = val;
                if (val > mxdist)
                {
                        k = i;
                        mxdist = val;
                }
        }
        r = mxdist;
        for (int i = 0; i < n; i++)
        {
                if (i == j || i == k)
                        continue;
                int da = ldist[i];
                int db = getDistance(i, k);
                rdist[i] = db;
                int change = (da + db - mxdist) / 2;
                r = min(r, max(da - change, db - change));
        }
        if (sub <= 2)
                return r;
        ll.pb(j);
        rr.pb(k);
        for (int i = 0; i < n; i++)
        {
                if (i == j || i == k)
                        continue;
                int change = (ldist[i] + rdist[i] - mxdist) / 2;
                if (r == max(ldist[i] - change, rdist[i] - change) && ldist[i] <= rdist[i])
                        ml.pb(i);
                else if (r == max(ldist[i] - change, rdist[i] - change))
                        mr.pb(i);
                else if (ldist[i] < rdist[i])
                        ll.pb(i);
                else if (ldist[i] > rdist[i])
                        rr.pb(i);
                else
                        assert(false);
        }
        if (ll.size() > (n/2) || rr.size() > (n/2))
                return -r;
        if (ml.size() <= (n/2) && mr.size() <= (n/2))
                return r;
        bool res;
        if (ml.size() > mr.size())
                res = check(ml, ldist);
        else
                res = check(mr, rdist);
        if (res)
                return r;
        else
                return -r;
}

Compilation message (stderr)

towns.cpp: In function 'bool check(const std::vector<int>&, int*)':
towns.cpp:38:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for (int i = 0; i < v.size(); i++)
      |                         ~~^~~~~~~~~~
towns.cpp:40:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |                 for (int j = i+1; j < v.size(); j++)
      |                                   ~~^~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:115:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  115 |         if (ll.size() > (n/2) || rr.size() > (n/2))
      |             ~~~~~~~~~~^~~~~~~
towns.cpp:115:44: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  115 |         if (ll.size() > (n/2) || rr.size() > (n/2))
      |                                  ~~~~~~~~~~^~~~~~~
towns.cpp:117:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  117 |         if (ml.size() <= (n/2) && mr.size() <= (n/2))
      |             ~~~~~~~~~~^~~~~~~~
towns.cpp:117:45: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  117 |         if (ml.size() <= (n/2) && mr.size() <= (n/2))
      |                                   ~~~~~~~~~~^~~~~~~~

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