Submission #802491

#	Time	Username	Problem	Language	Result	Execution time	Memory
802491		caganyanmaz	Towns (IOI15_towns)	C++17	25 / 100	12 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 fdist[MXSIZE];


bool connected(int i, int j, int* dist, int cndist)
{
        int cdist;
        if (!i)
                cdist = fdist[j];
        if (!j)
                cdist = fdist[i];
        else
                cdist = getDistance(i, j);
        bool res = dist[i] + dist[j] > (cdist + cndist * 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, int cndist)
{
        for (int i = 0; i < v.size(); i++)
        {
                for (int j = i+1; j < v.size(); j++)
                {
                        if (connected(v[i], v[j], dist, cndist))
                        {

                                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);
                fdist[i] = val;
                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;
                }
        }
        int 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;
        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;
        bool res;
        int cndist;
        if ((ll.size() + ml.size()) > (rr.size() + mr.size()))
        {
                if (ml.empty())
                {
                        res = true;
                }
                else
                {
                        cndist = ldist[ml[0]] - rdist[ml[0]] + r;
                        res = check(ml, ldist, cndist);
                }
        }
        else
        {
                if (mr.empty())
                {
                        res = true;
                }
                else
                {
                        cndist = rdist[mr[0]] - ldist[mr[0]] + r;
                        res = check(mr, rdist, cndist);
                }
        }
        if (res)
                return r;
        else
                return -r;
}

Compilation message (stderr)

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