Submission #1051924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051924		Zicrus	Towns (IOI15_towns)	C++17	0 / 100	1 ms	348 KiB

towns

#include <bits/stdc++.h>
#include "towns.h"
using namespace std;

typedef long long ll;

struct node {
    vector<pair<ll, node*>> adj;
    pair<ll, node*> parent;
    int id;
    node(int id = -1) {
        this->id = id;
    }
};

vector<vector<ll>> dist;
unordered_set<node*> graph;
ll cnt;

ll R;

ll getDist(node *a, node *b) {
    ll offset = 0;
    while (!a->adj.empty()) {
        offset += a->adj.front().first;
        a = a->adj.front().second;
    }
    while (!b->adj.empty()) {
        offset += b->adj.front().first;
        b = b->adj.front().second;
    }
    return dist[a->id][b->id] - offset;
}

pair<bool, ll> compatible(node *a, node *b) {
    ll offset = 1ll << 62ll;
    for (auto &c : graph) {
        if (c->id == a->id || c->id == b->id) continue;
        if (offset == 1ll << 62ll) {
            offset = getDist(a, c) - getDist(b, c);
            if ((getDist(a, b) - offset) / 2 == 0 ||
                (getDist(a, b) - offset) / 2 + offset == 0) {
                return {false, 0};
            }
            continue;
        }
        if (getDist(a, c) - getDist(b, c) != offset) return {false, 0};
    }
    return {true, offset};
}

vector<pair<ll, node*>> getAll(pair<node*, node*> p, ll offset) {
    vector<pair<ll, node*>> res = {{(getDist(p.first, p.second) - offset) / 2 + offset, p.first},
                                   {(getDist(p.first, p.second) - offset) / 2, p.second}};
    for (auto &e : graph) {
        bool has = false;
        for (auto &h : res) {
            if (h.second->id == e->id) {
                has = true;
                break;
            }
        }
        if (has) continue;

        ll o = 1ll << 62ll;
        bool match = true;
        for (auto &c : graph) {
            if (c->id == e->id || c->id == p.first->id) continue;

            if (o == 1ll << 62ll) {
                o = getDist(p.first, c) - getDist(e, c);
                if ((getDist(p.first, e) - o) / 2 == 0 ||
                    (getDist(p.first, e) - o) / 2 + o == 0) {
                    match = false;
                    break;
                }
                continue;
            }
            if (getDist(p.first, c) - getDist(e, c) != o) {
                match = false;
                break;
            }
        }
        if (match) {
            res.push_back({(getDist(p.first, e) - o) / 2, e});
        }
    }
    return res;
}

vector<pair<ll, node*>> reduce() {
    for (auto &a : graph) {
        for (auto &b : graph) {
            if (a->id <= b->id) continue;
            auto p = compatible(a, b);
            if (p.first) {
                return getAll({a, b}, p.second);
            }
        }
    }
    return {};
}

ll dfs2(node *cur, ll parId) {
    if (cur->id >= 0) return 0;
    ll mx = 0;
    for (auto &e : cur->adj) {
        if (e.second->id == parId) continue;
        mx = max(mx, e.first + dfs2(e.second, cur->id));
    }
    if (cur->parent.first == 0 || cur->parent.second->id == parId) return mx;
    return max(mx, cur->parent.first + dfs2(cur->parent.second, cur->id));
}

void dfs1(node *cur) {
    if (cur->id < 0) {
        R = min(R, dfs2(cur, 1ll << 62ll));
    }
    for (auto &e : cur->adj) {
        dfs1(e.second);
    }
}

int hubDistance(int n, int sub) {
    graph.clear();
    R = 1ll << 62ll;
    dist = vector<vector<ll>>(n, vector<ll>(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);
        }
    }

    cnt = -1;
    for (int i = 0; i < n; i++) {
        node *d = new node(i);
        graph.insert(d);
    }

    while (graph.size() > 1) {
        vector<pair<ll, node*>> p = reduce();
        if (p.size() == graph.size()-1) {
            for (auto &e : p) graph.erase(e.second);
            for (auto &e : p) {
                e.second->parent = {e.first, *graph.begin()};
                (*graph.begin())->adj.push_back(e);
            }
            break;
        }
        node *nw = new node(cnt--);
        nw->adj = p;
        graph.insert(nw);
        for (auto &e : p) {
            e.second->parent = {e.first, nw};
            graph.erase(e.second);
        }
    }

    dfs1(*graph.begin());

    return R;
}

Compilation message (stderr)

towns.cpp: In constructor 'node::node(int)':
towns.cpp:11:14: warning: declaration of 'id' shadows a member of 'node' [-Wshadow]
   11 |     node(int id = -1) {
      |          ~~~~^~~~~~~
towns.cpp:10:9: note: shadowed declaration is here
   10 |     int id;
      |         ^~
towns.cpp: In constructor 'node::node(int)':
towns.cpp:11:14: warning: declaration of 'id' shadows a member of 'node' [-Wshadow]
   11 |     node(int id = -1) {
      |          ~~~~^~~~~~~
towns.cpp:10:9: note: shadowed declaration is here
   10 |     int id;
      |         ^~
towns.cpp: In constructor 'node::node(int)':
towns.cpp:11:14: warning: declaration of 'id' shadows a member of 'node' [-Wshadow]
   11 |     node(int id = -1) {
      |          ~~~~^~~~~~~
towns.cpp:10:9: note: shadowed declaration is here
   10 |     int id;
      |         ^~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:150:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  150 |         node *nw = new node(cnt--);
      |                             ~~~^~
towns.cpp:161:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  161 |     return R;
      |            ^
towns.cpp:124:28: warning: unused parameter 'sub' [-Wunused-parameter]
  124 | 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