Submission #552931

#	Time	Username	Problem	Language	Result	Execution time	Memory
552931		elazarkoren	Towns (IOI15_towns)	C++17	0 / 100	2 ms	468 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 = 305;
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(par.size());
        sz.push_back(1);
        n++;
    }
};

Dsu dsu;

bool Merge(int v, int u, vi &nodes) {
    if (dsu.Find(v) == dsu.Find(u)) return false;
    pii p = {-1, -1};
    for (int k : nodes) {
        if (dist[u][v] + dist[v][k] == dist[u][k] || dist[u][v] + dist[u][k] == dist[v][k]) continue;
//        if (dsu.Find(u) == dsu.Find(k) || dsu.Find(v) == dsu.Find(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};
    }
    dsu.Union(u, v);
    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 {
        dsu.Add();
        par[u] = par[v] = sz;
        dsu.Union(sz, u);
        nodes.push_back(sz);
        for (int i = 0; i < sz; i++) {
            dist[i][sz] = dist[sz][i] = dist[u][i] - par_dist[u];
        }
        dist[u][sz] = dist[sz][u] = par_dist[u];
        sz++;
    }
    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(n);
    vi nodes(n);
    sz = n;
    for (int i = 0; i < n; i++) nodes[i] = i;
    for (int i = 0; i < sz; i++) {
        for (int j = 0; j < sz; j++) {
            Merge(nodes[i], nodes[j], nodes);
        }
    }
    vi remain;
    for (int i = 0; i < sz; i++) {
        if (!par[i]) remain.push_back(i);
    }
    if (remain.size() > 1) par[remain.back()] = remain[0];
    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]});
        }
    }
    int ans = infinity;
    for (int i = 0; i < sz; i++) {
        chkmin(ans, Dfs(tree, i, -1));
    }
    return ans;
}

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 member function 'void Dsu::Add()':
towns.cpp:46:31: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
   46 |         par.push_back(par.size());
      |                       ~~~~~~~~^~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:99:28: warning: unused parameter 'sub' [-Wunused-parameter]
   99 | 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