| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1051879 |
2024-08-10T10:22:50 Z |
Zicrus |
Towns (IOI15_towns) |
C++17 |
|
0 ms |
348 KB |
#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) {
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());
throw;
return R;
}
Compilation message
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:149:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
149 | node *nw = new node(cnt--);
| ~~~^~
towns.cpp:162:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
162 | return R;
| ^
towns.cpp:124:28: warning: unused parameter 'sub' [-Wunused-parameter]
124 | int hubDistance(int n, int sub) {
| ~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
