Submission #1072392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072392		Zicrus	Towns (IOI15_towns)	C++17	0 / 100	8 ms	1220 KiB

towns

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

typedef long long ll;

ll idkLol = 0;

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

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

queue<node*> delQ;

ll R;

ll getDist(node *a, node *b) {
    ll offset = 0;
    while (a->id < 0) {
        offset += a->adj.front().first;
        a = a->adj.front().second;
    }
    while (b->id < 0) {
        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};
    }
    if (offset == 1ll << 62ll) 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() {
    if (graph.size() == 2) {
        return {{getDist(*graph.begin(), *(++graph.begin())), *graph.begin()}};
    }

    node *x = nullptr, *y = nullptr, *z = nullptr;
    for (auto &a : graph) {
        for (auto &b : graph) {
            if (a->id <= b->id) continue;
            if (getDist(a, b) == 0) {
                node *nw = new node(cnt--);
                delQ.push(nw);
                nw->adj = a->adj;
                for (auto &e : b->adj) nw->adj.push_back(e);
                for (auto &e : nw->adj) e.second->parent = {e.first, nw};
                x = a; y = b; z = nw;
                goto idk;
            }
        }
    }
    idk:
    if (x != nullptr) graph.erase(x);
    if (y != nullptr) graph.erase(y);
    if (z != nullptr) graph.insert(z);

    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);
        delQ.push(d);
        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--);
        delQ.push(nw);
        nw->adj = p;
        graph.insert(nw);
        for (auto &e : p) {
            e.second->parent = {e.first, nw};
            graph.erase(e.second);
        }
    }

    dfs1(*graph.begin());
    while (!delQ.empty()) {
        delete delQ.front();
        delQ.pop();
    }

    return R;
}

Compilation message (stderr)

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