Submission #552960

#	Time	Username	Problem	Language	Result	Execution time	Memory
552960		elazarkoren	도시들 (IOI15_towns)	C++17	0 / 100	26 ms	540 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 infinity = 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;
    }
//    void Add() {
//        par.push_back(n);
//        sz.push_back(1);
//        n++;
//    }
};

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];
            }
        }
        dist[u][sz] = dist[sz][u] = 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;
}

int hubDistance(int N, int 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);
    vi nodes(n);
    nodes.reserve(300);
    sz = n;
    for (int i = 0; i < sz; i++) {
        for (int j = 0; j < sz; j++) {
            Merge(i, j);
        }
    }
    int ans = infinity;
    vi remain;
    for (int i = 0; i < sz; i++) {
        if (!par[i]) remain.push_back(i);
    }
    int root = remain[0];
    vector<vii> tree(sz);
    for (int i = 0; i < sz; i++) {
        if (i != root) {
            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 = 0; i < sz; i++) {
        int curr = 0;
        for (int j = 0; j < n; j++) chkmax(curr, dist[j][i]);
        chkmin(ans, curr);
    }
    return ans;
}
//1 2
//6
//0 2 4 4 4 4
//2 0 4 4 4 4
//4 4 0 2 4 4
//4 4 2 0 4 4
//4 4 4 4 0 2
//4 4 4 4 2 0

//1 1
//6
//0 3 4 5 6 7
//3 0 3 4 5 6
//4 3 0 3 4 5
//5 4 3 0 3 4
//6 5 4 3 0 3
//7 6 5 4 3 0

Compilation message (stderr)

towns.cpp: In constructor 'Dsu::Dsu(int)':
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(int)':
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(int)':
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 'int hubDistance(int, int)':
towns.cpp:102:28: warning: unused parameter 'sub' [-Wunused-parameter]
  102 | int hubDistance(int N, int 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