# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
41912 |
2018-02-22T05:58:02 Z |
funcsr |
Towns (IOI15_towns) |
C++14 |
|
10 ms |
8712 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
#define MAX_V 1000
int dist[MAX_V][MAX_V];
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) {
for (int u : nokori) {
vector<int> rs;
rs.pb(u);
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;
for (int x : vs) if (x != vs[0]) same = false;
if (same) rs.pb(v);
}
if (rs.size() < 2) continue;
//cout<<"{";for (int x : rs)cout<<x<<",";cout<<"}\n";
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;
nokori.insert(root);
break;
}
}
//return 0;
//assert(V <= MAX_V);
rep(i, V) sort(all(G[i])), uniq(G[i]);
rep(i, N) assert(G[i].size() == 1);
rep(i, V) if (i >= N) assert(G[i].size() >= 3);
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:45:13: warning: unused variable 'l' [-Wunused-variable]
int l = dist[u][v];
^
towns.cpp: At global scope:
towns.cpp:33:28: warning: unused parameter 'sub' [-Wunused-parameter]
int hubDistance(int N, int sub) {
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
9 ms |
8312 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 |
4 ms |
8396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
10 ms |
8504 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 |
4 ms |
8608 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
10 ms |
8712 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 |
4 ms |
8712 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |