oj.uz

Submission #727165

# Submission time Handle Problem Language Result Execution time Memory
727165 2023-04-20T06:39:05 Z becaido Towns (IOI15_towns) C++17
100 / 100
 16 ms 1108 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "towns.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout (T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

#ifdef WAIMAI
static int _N;
static int _dist[110][110];
static int _quota, _user_query;

void _ini_query(int N, int k) {
    int ret;
    _N = N;
    for (int i = 0; i < _N; i++)
        for (int j = 0; j < _N; j++)  {
	    ret = scanf("%d", &_dist[i][j]);
            assert(ret == 1);
        }
    if (k == 1 || k == 3) _quota = _N * (_N - 1) / 2;
    else if (k == 2 || k == 4 || k == 6) _quota = (7 * _N + 1) / 2;
    else _quota = 5 * _N;
    _user_query = 0;
}

int getDistance(int i, int j) {
    _user_query++;
    if (_user_query > _quota) {
        printf("0\n");
        exit(0);
    }
    if (i < 0 || i >= _N) return 0;
    if (j < 0 || j >= _N) return 0;
    return _dist[i][j];
}
#endif

const int SIZE = 120;

int n, A, B, cr;
int dis[SIZE][SIZE];
int d[SIZE], r[SIZE];

inline int D(int a, int b) {
    if (a == b) return 0;
    if (dis[a][b]) return dis[a][b];
    return dis[a][b] = dis[b][a] = getDistance(a, b);
}

inline bool same(int a, int b) {
    if (r[b] != cr) swap(a, b);
    if (r[a] < cr) return r[b] < cr;
    if (r[a] > cr) return r[b] > cr;
    return d[a] + d[b] != D(a, b);
}

int hubDistance(int N, int sub) {
    n = N;
    FOR (i, 0, n - 1) fill(dis[i], dis[i] + n, 0);
    A = B = 0;
    FOR (i, 0, n - 1) if (D(0, i) > D(0, A)) A = i;
    FOR (i, 0, n - 1) if (D(A, i) > D(A, B)) B = i;
    int mn = INT_MAX;
    FOR (i, 0, n - 1) {
        d[i] = (D(0, i) + D(A, i) - D(0, A)) / 2;
        r[i] = D(A, i) - d[i];
        mn = min(mn, max(r[i], D(A, B) - r[i]));
    }
    vector<int> vc;
    FOR (i, 0, n - 1) if (max(r[i], D(A, B) - r[i]) == mn) vc.pb(r[i]);
    sort(vc.begin(), vc.end());
    vc.erase(unique(vc.begin(), vc.end()), vc.end());
    if (vc.size() > 1) {
        int cnt = 0;
        FOR (i, 0, n - 1) cnt += r[i] <= vc[0];
        if (cnt * 2 <= n) swap(vc[0], vc[1]);
    }
    cr = vc[0];
    vector<pair<int, int>> cur, die;
    FOR (i, 0, n - 1) cur.pb(i, 1);
    while (cur.size() > 1) {
        vector<pair<int, int>> tmp;
        for (int i = 0; i + 1 < cur.size(); i += 2) {
            if (same(cur[i].F, cur[i + 1].F)) tmp.pb(cur[i].F, cur[i].S + cur[i + 1].S);
            else {
                if (cur[i].S < cur[i + 1].S) swap(cur[i], cur[i + 1]);
                if (cur[i].S == cur[i + 1].S) die.pb(cur[i]), die.pb(cur[i + 1]);
                else tmp.pb(cur[i].F, cur[i].S - cur[i + 1].S), die.pb(cur[i].F, cur[i + 1].S), die.pb(cur[i + 1]);
            }
        }
        if (cur.size() & 1) tmp.pb(cur.back());
        cur = tmp;
    }
    if (cur.size() == 0) return max(cr, D(A, B) - cr);
    int cnt = cur[0].S;
    for (auto [x, c] : die) if (same(cur[0].F, x)) cnt += c;
    return (cnt * 2 <= n ? 1 : -1) * max(cr, D(A, B) - cr);
}

/*
in1
1 1
11
0 17 18 20 17 12 20 16 23 20 11
17 0 23 25 22 17 25 21 28 25 16
18 23 0 12 21 16 24 20 27 24 17
20 25 12 0 23 18 26 22 29 26 19
17 22 21 23 0 9 21 17 26 23 16
12 17 16 18 9 0 16 12 21 18 11
20 25 24 26 21 16 0 10 29 26 19
16 21 20 22 17 12 10 0 25 22 15
23 28 27 29 26 21 29 25 0 21 22
20 25 24 26 23 18 26 22 21 0 19
11 16 17 19 16 11 19 15 22 19 0
out1
16
*/

#ifdef WAIMAI
int main() {
    int ncase, R, N;
    int subtask;
    int ret;
    cin >> subtask >> ncase;
    for (int i = 0; i < ncase; i++) {
        cin >> N;
        _ini_query(N,subtask);
        R=hubDistance(N,subtask);
        cout << R << '\n';
    }
    return 0;
}
#endif

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:102:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for (int i = 0; i + 1 < cur.size(); i += 2) {
      |                         ~~~~~~^~~~~~~~~~~~
towns.cpp:76:28: warning: unused parameter 'sub' [-Wunused-parameter]
   76 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 980 KB Output is correct
2 Correct 16 ms 852 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 14 ms 844 KB Output is correct
5 Correct 13 ms 944 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 980 KB Output is correct
2 Correct 10 ms 852 KB Output is correct
3 Correct 14 ms 904 KB Output is correct
4 Correct 14 ms 980 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 852 KB Output is correct
2 Correct 13 ms 852 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 14 ms 848 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 852 KB Output is correct
2 Correct 14 ms 828 KB Output is correct
3 Correct 14 ms 852 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 852 KB Output is correct
2 Correct 14 ms 852 KB Output is correct
3 Correct 13 ms 852 KB Output is correct