oj.uz

Submission #494889

# Submission time Handle Problem Language Result Execution time Memory
494889 2021-12-17T08:18:09 Z thecodingwizard Towns (IOI15_towns) C++11
100 / 100
 20 ms 848 KB 
#include <bits/stdc++.h>
#include "towns.h"

using namespace std;

#define ii pair<int, int>
#define mp make_pair
#define inf 1e9;
#define f first
#define s second
#define pb push_back

map<ii, int> cached;
int getD(int a, int b) {
    if (a == b) return 0;
    if (a > b) swap(a, b);
    if (cached.count(mp(a, b))) return cached[mp(a, b)];
    return cached[mp(a, b)] = getDistance(a, b);
}

int hubDistance(int N, int sub) {
    cached.clear();

    int u, v;

    int maxDist = -1;
    for (int i = 0; i < N; i++) {
        if (getD(0, i) > maxDist) {
            maxDist = getD(0, i);
            u = i;
        }
    }

    maxDist = -1;
    for (int i = 0; i < N; i++) {
        if (getD(u, i) > maxDist) {
            maxDist = getD(u, i);
            v = i;
        }
    }

    int radius = inf;
    int d1 = -1, d2 = -1;
    for (int i = 0; i < N; i++) {
        int distFromHubToU = (getD(u, i) + getD(u, 0) - getD(i, 0))/2;
        int distFromHubToV = getD(u, v) - distFromHubToU;
        if (max(distFromHubToU, distFromHubToV) < radius) {
            radius = max(distFromHubToU, distFromHubToV);
            d1 = distFromHubToU;
            d2 = -1;
        } else if (max(distFromHubToU, distFromHubToV) == radius) {
            if (distFromHubToU != d1) {
                d2 = distFromHubToU;
            }
        }
    }
    if (d2 != -1 && d1 > d2) swap(d1, d2);

    bool balanced = true;
    map<int, int> frequency;
    for (int i = 0; i < N; i++) {
        int distFromU = (getD(u, i) + getD(u, 0) - getD(0, i))/2;
        frequency[distFromU]++;
    }

    int ct1 = 0;
    int ct2 = 0;
    for (auto x : frequency) {
        if (x.f <= d1) ct1 += x.s;
        if (x.f <= d2) ct2 += x.s;
    }
    // cout << ct1 << " " << ct2 << " "<< d1 << " "<< d2 << endl;
    bool isHub2 = false;
    if (ct1 - frequency[d1] > N/2) balanced = false;
    if (ct1 < N/2) {
        if (d2 != -1) {
            if (ct2 - frequency[d2] <= N/2 && ct2 >= N/2) {
                isHub2 = true;
            }
            else balanced = false;
        } else {
            balanced = false;
        }
    }
    if (balanced) {
        int distToHub = -1;
        if (isHub2) {
            distToHub = d2;
        } else {
            distToHub = d1;
        }
        vector<int> nodes;
        for (int i = 0; i < N; i++) {
            int distFromU = (getD(u, i) + getD(u, 0) - getD(0, i))/2;
            if (distFromU != distToHub) continue;
            nodes.pb(i);
        }

        int tgt = 0;
        vector<int> stackA, stackB;
        stackB.pb(0);
        for (int i = 0; i < nodes.size() - 1; i++) {
            int a = nodes[tgt], b = nodes[i+1];
            bool same = getD(a, u) + getD(b, u) - getD(a, b) != distToHub*2;
            if (same) {
                stackB.pb(i+1);
            } else {
                stackA.pb(stackB.back());
                stackB.pop_back();
                if (stackB.empty()) {
                    tgt = i+1;
                    stackB.pb(i+1);
                } else {
                    stackA.pb(i+1);
                }
            }
        }
        if (tgt < nodes.size()) {
            int sz = stackB.size();
            while (!stackA.empty()) {
                int x = stackA.back();
                stackA.pop_back();
                int a = nodes[x], b = nodes[tgt];
                bool same = getD(a, u) + getD(b, u) - getD(a, b) != distToHub*2;
                if (same) {
                    sz++;
                    if (!stackA.empty()) stackA.pop_back();
                } else {
                    if (stackB.empty()) break;
                    stackB.pop_back();
                }
            }
            if (sz > N/2) balanced = false;
        }
    }

    return (balanced ? 1 : -1) * radius;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:102:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for (int i = 0; i < nodes.size() - 1; i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~
towns.cpp:118:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         if (tgt < nodes.size()) {
      |             ~~~~^~~~~~~~~~~~~~
towns.cpp:119:33: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  119 |             int sz = stackB.size();
      |                      ~~~~~~~~~~~^~
towns.cpp:21:28: warning: unused parameter 'sub' [-Wunused-parameter]
   21 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~
towns.cpp:124:46: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
  124 |                 bool same = getD(a, u) + getD(b, u) - getD(a, b) != distToHub*2;
      |                                          ~~~~^~~~~~
towns.cpp:46:34: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |         int distFromHubToV = getD(u, v) - distFromHubToU;
      |                              ~~~~^~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 332 KB Output is correct
2 Correct 13 ms 356 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 16 ms 364 KB Output is correct
5 Correct 18 ms 368 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 460 KB Output is correct
2 Correct 11 ms 332 KB Output is correct
3 Correct 18 ms 368 KB Output is correct
4 Correct 18 ms 364 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 332 KB Output is correct
2 Correct 18 ms 364 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 16 ms 368 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 332 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 332 KB Output is correct
2 Correct 17 ms 360 KB Output is correct
3 Correct 17 ms 332 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 360 KB Output is correct
2 Correct 20 ms 364 KB Output is correct
3 Correct 19 ms 848 KB Output is correct