| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 41892 |
2018-02-22T05:31:00 Z |
funcsr |
Towns (IOI15_towns) |
C++14 |
|
1000 ms |
524288 KB |
#include "towns.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cassert>
#include <set>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back
#define _1 first
#define _2 second
#define INF 1145141919
#define MOD 1000000007
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define MAX_V 300
int dist[MAX_V][MAX_V];
int U[MAX_V], R[MAX_V];
int find(int x) {
if (U[x] == x) return x;
return U[x] = find(U[x]);
}
void unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (R[x] < R[y]) swap(x, y);
U[y] = x;
R[x] += R[y];
}
vector<P> G[MAX_V];
int dfs(int x, int p, int r) {
int ret = r;
for (P pp : G[x]) if (pp._1 != p) {
int t = pp._1, len = pp._2;
ret = max(ret, dfs(t, x, r+len));
}
return ret;
}
int hubDistance(int N, int sub) {
rep(i, MAX_V) rep(j, MAX_V) dist[i][j] = 0;
rep(i, N) rep(j, i) dist[i][j] = dist[j][i] = getDistance(i, j);
set<int> nokori;
rep(i, N) nokori.insert(i);
int V = N;
while (nokori.size() >= 2) {
rep(i, V) U[i] = i, R[i] = 1;
int u = *nokori.begin();
if (nokori.size() > 2) {
for (int v : nokori) if (u != v) {
int l = dist[u][v];
vector<int> vs;
for (int x : nokori) if (x != u && x != v) vs.pb(dist[x][u]-dist[x][v]);
bool same = true;
assert(vs.size());
for (int x : vs) if (x != vs[0]) same = false;
if (same) unite(u, v);
}
}
else {
unite(*nokori.begin(), *nokori.rbegin());
}
vector<int> rs;
for (int x : nokori) if (find(u) == find(x)) rs.pb(x);
assert(rs.size() >= 2);
int x0 = rs[0], x1 = rs[1];
for (int x : rs) nokori.erase(x);
if (nokori.empty()) assert(rs.size() >= 3);
int tekitou = -1;
if (nokori.empty()) tekitou = rs[2];
else tekitou = *nokori.begin();
int sum = dist[x0][x1], diff = dist[x0][tekitou] - dist[x1][tekitou];
int a = (sum+diff)/2;
int root = V++;
G[root].pb(P(x0, a));
G[x0].pb(P(root, a));
dist[x0][root] = dist[root][x0] = a;
for (int x : rs) if (x != x0) {
int d = dist[x0][x] - a;
dist[x][root] = dist[root][x] = d;
G[root].pb(P(x, d));
G[x].pb(P(root, d));
}
for (int x : nokori) dist[root][x] = dist[x][root] = dist[x0][x] - a;
assert(V <= MAX_V);
nokori.insert(root);
}
int R = INF;
rep(i, V) {
R = min(R, dfs(i, -1, 0));
}
return R;
}
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:55:13: warning: unused variable 'l' [-Wunused-variable]
int l = dist[u][v];
^
towns.cpp:92:7: warning: declaration of 'R' shadows a global declaration [-Wshadow]
int R = INF;
^
towns.cpp:21:15: note: shadowed declaration is here
int U[MAX_V], R[MAX_V];
^
towns.cpp: At global scope:
towns.cpp:43:28: warning: unused parameter 'sub' [-Wunused-parameter]
int hubDistance(int N, int sub) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1103 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
524288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
25 ms |
524288 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
524288 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
524288 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
524288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
