Submission #612461

#	Time	Username	Problem	Language	Result	Execution time	Memory
612461		yuto1115	Towns (IOI15_towns)	C++17	48 / 100	21 ms	4296 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; --i)
#define rrep2(i, n, t) for(ll i = ll(n)-1; i >= ll(t); --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int hubDistance(int n, int sub) {
    int a, b;
    vi da(n), db(n);
    int dm;
    vvp ls;
    {
        int mx = 0, id = -1;
        rep(i, n) if (chmax(mx, getDistance(0, i))) id = i;
        assert(id != -1);
        a = id;
    }
    {
        int mx = 0, id = -1;
        rep(i, n) {
            da[i] = getDistance(a, i);
            if (chmax(mx, da[i])) id = i;
        }
        assert(id != -1);
        b = id;
        dm = mx;
        rep(i, n) db[i] = getDistance(b, i);
        ls.resize(dm);
    }
    rep(i, n) {
        if (i == a or i == b) continue;
        int x = (da[i] - db[i] + dm) / 2;
        int y = (da[i] + db[i] - dm) / 2;
        ls[x].eb(i, y);
    }
    int r = inf;
    rep(i, dm) {
        if (ls[i].empty()) continue;
        chmin(r, max<int>(i, dm - i));
    }
    if (sub <= 2) {
        return r;
    } else if (sub == 4) {
        bool ex = false;
        rep(i, dm) {
            if (ls[i].empty()) continue;
            if (max(i, dm - i) != r) continue;
            {
                int sum = 1;
                rep(j, i) sum += SZ(ls[j]);
                if (sum * 2 > n) continue;
            }
            {
                int sum = 1;
                rep2(j, i + 1, dm) sum += SZ(ls[j]);
                if (sum * 2 > n) continue;
            }
            if (SZ(ls[i]) * 2 > n) continue;
            ex = true;
        }
        return (ex ? r : -r);
    } else {
        bool ex = false;
        rep(i, dm) {
            if (ls[i].empty()) continue;
            if (max(i, dm - i) != r) continue;
            {
                int sum = 1;
                rep(j, i) sum += SZ(ls[j]);
                if (sum * 2 > n) continue;
            }
            {
                int sum = 1;
                rep2(j, i + 1, dm) sum += SZ(ls[j]);
                if (sum * 2 > n) continue;
            }
            if (SZ(ls[i]) * 2 <= n) {
                ex = true;
                break;
            }
            vvp div;
            for (P p: ls[i]) {
                bool flag = false;
                rep(j, SZ(div)) {
                    P np = div[j].back();
                    if (getDistance(p.first, np.first) < p.second + np.second) {
                        flag = true;
                        div[j].pb(p);
                        break;
                    }
                }
                if (!flag) div.pb({p});
            }
            int mx = 0;
            rep(j, SZ(div)) chmax(mx, SZ(div[j]));
            if (mx * 2 <= n) ex = true;
        }
        return (ex ? r : -r);
    }
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:51:48: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   51 |         rep(i, n) if (chmax(mx, getDistance(0, i))) id = i;
      |                                                ^
towns.cpp:51:58: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   51 |         rep(i, n) if (chmax(mx, getDistance(0, i))) id = i;
      |                                                          ^
towns.cpp:58:36: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   58 |             da[i] = getDistance(a, i);
      |                                    ^
towns.cpp:59:40: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   59 |             if (chmax(mx, da[i])) id = i;
      |                                        ^
towns.cpp:64:42: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   64 |         rep(i, n) db[i] = getDistance(b, i);
      |                                          ^
towns.cpp:76:27: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   76 |         chmin(r, max<int>(i, dm - i));
      |                           ^
towns.cpp:76:33: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   76 |         chmin(r, max<int>(i, dm - i));
      |                              ~~~^~~

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