Submission #552980

#	Time	Username	Problem	Language	Result	Execution time	Memory
552980		elazarkoren	Towns (IOI15_towns)	C++17	0 / 100	21 ms	704 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
#define int ll
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;

const int MAX_N = 205;
const int inf = 1e9;

int dist[MAX_N][MAX_N];
int par_dist[MAX_N];
int par[MAX_N];

int n;
int sz;

struct Dsu {
    int n;
    vi par, sz;
    Dsu() {}
    Dsu(int n): n(n) {
        par.resize(n), sz.resize(n, 1);
        for (int i = 0; i < n; i++) par[i] = i;
    }
    int Find(int i) {
        return par[i] == i ? i : par[i] = Find(par[i]);
    }
    void Union(int a, int b) {
        int pa = Find(a), pb = Find(b);
        if (pa == pb) return;
        if (sz[pa] < sz[pb]) swap(pa, pb);
        sz[pa] += sz[pb];
        par[pb] = pa;
    }
};

Dsu dsu;

bool Merge(int v, int u) {
    if (dsu.Find(v) == dsu.Find(u)) return false;
    pii p = {-1, -1};
    for (int k = 0; k < sz; k++) {
        if (dist[u][v] + dist[v][k] == dist[u][k] || dist[u][v] + dist[u][k] == dist[v][k]) continue;
        int a1 = dist[v][u];
        int a2 = dist[v][k];
        int a3 = dist[u][k];
        int z = (a2 + a3 - a1) / 2;
        int x = a2 - z, y = a3 - z;
        if (p.x != -1) {
            if (x != p.x && y != p.y) return false;
        }
        if (x < 0 || y < 0) return false;
        p = {x, y};
    }
    par_dist[v] = p.x, par_dist[u] = p.y;
    if (par[u]) {
        par[v] = par[u];
    } else if (par[v]) {
        par[u] = par[v];
    } else {
        par[u] = par[v] = sz;
        dsu.Union(sz, u);
        for (int i = 0; i < sz; i++) {
            if (dsu.Find(u) == dsu.Find(i)) {
                dist[i][sz] = dist[sz][i] = dist[i][u] + par_dist[u];
            } else {
                dist[i][sz] = dist[sz][i] = dist[u][i] - par_dist[u];
            }
        }
        sz++;
    }
    dsu.Union(u, v);
    return true;
}

int Dfs(vector<vii> &tree, int node, int parent) {
    int ans = 0;
    for (auto [neighbor, d] : tree[node]) {
        if (neighbor != parent) {
            chkmax(ans, d + Dfs(tree, neighbor, node));
        }
    }
    return ans;
}

int32_t hubDistance(int32_t N, int32_t sub) {
    n = N;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            dist[i][j] = dist[j][i] = getDistance(i, j);
        }
    }
    dsu = Dsu(3 * n);
    sz = n;
    for (int i = 0; i < sz; i++) {
        for (int j = 0; j < sz; j++) {
            Merge(i, j);
        }
    }
    int ans = inf;
    vector<vii> tree(sz);
    for (int i = 0; i < sz; i++) {
        if (par[i]) {
            tree[par[i]].push_back({i, par_dist[i]});
            tree[i].push_back({par[i], par_dist[i]});
        }
        par[i] = par_dist[i] = 0;
    }
    for (int i = n; i < sz; i++) {
        int curr = 0;
        for (int j = 0; j < n; j++) chkmax(curr, dist[j][i]);
        chkmin(ans, curr);
    }
    return ans;
}

Compilation message (stderr)

towns.cpp: In constructor 'Dsu::Dsu(ll)':
towns.cpp:31:13: warning: declaration of 'n' shadows a member of 'Dsu' [-Wshadow]
   31 |     Dsu(int n): n(n) {
      |             ^
towns.cpp:28:9: note: shadowed declaration is here
   28 |     int n;
      |         ^
towns.cpp: In constructor 'Dsu::Dsu(ll)':
towns.cpp:31:13: warning: declaration of 'n' shadows a member of 'Dsu' [-Wshadow]
   31 |     Dsu(int n): n(n) {
      |             ^
towns.cpp:28:9: note: shadowed declaration is here
   28 |     int n;
      |         ^
towns.cpp: In constructor 'Dsu::Dsu(ll)':
towns.cpp:31:13: warning: declaration of 'n' shadows a member of 'Dsu' [-Wshadow]
   31 |     Dsu(int n): n(n) {
      |             ^
towns.cpp:28:9: note: shadowed declaration is here
   28 |     int n;
      |         ^
towns.cpp: In function 'int32_t hubDistance(int32_t, int32_t)':
towns.cpp:100:51: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  100 |             dist[i][j] = dist[j][i] = getDistance(i, j);
      |                                                   ^
towns.cpp:100:54: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  100 |             dist[i][j] = dist[j][i] = getDistance(i, j);
      |                                                      ^
towns.cpp:124:12: warning: conversion from 'll' {aka 'long long int'} to 'int32_t' {aka 'int'} may change value [-Wconversion]
  124 |     return ans;
      |            ^~~
towns.cpp:96:40: warning: unused parameter 'sub' [-Wunused-parameter]
   96 | int32_t hubDistance(int32_t N, int32_t sub) {
      |                                ~~~~~~~~^~~

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