| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 778831 |
2023-07-10T18:53:19 Z |
danikoynov |
Towns (IOI15_towns) |
C++14 |
|
13 ms |
900 KB |
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 120;
int dist[maxn];
int par[maxn], rnk[maxn], path[maxn];
int table[maxn][maxn];
int getLocalDistance(int v, int u)
{
if (table[v][u] != 0)
return table[v][u];
table[v][u] = table[u][v] = getDistance(v, u);
return table[v][u];
}
int find_leader(int v)
{
if (par[v] == v)
return v;
return (par[v] = find_leader(par[v]));
}
bool unite(int v, int u)
{
v = find_leader(v);
u = find_leader(u);
if (v == u)
return false;
par[u] = v;
rnk[v] += rnk[u];
return true;
}
vector < int > get_biggest(vector < int > st, int mst)
{
cout << "biggest " << " " << st.size() << " " << mst << endl;
for (int v : st)
cout << rnk[find_leader(v)] << " ";
cout << endl;
if (st.size() == 1)
return st;
vector < int > res;
for (int v : st)
{
if (res.empty())
res.push_back(v);
else
{
int a = find_leader(res.back()), b = find_leader(v);
int part = (dist[a] + dist[b] - getLocalDistance(a, b)) / 2;
if (part != mst)
unite(a, b);
else
res.push_back(b);
}
}
while(res.size() > 1)
{
int a = find_leader(res[0]), b = find_leader(res.back());
int part = (dist[a] + dist[b] - getLocalDistance(a, b)) / 2;
if (part != mst)
unite(a, b), res.pop_back();
else
break;
}
vector < int > odd, even;
int sz1 = 0, sz2 = 0;
///cout << "fine" << endl;
for (int i = 0; i < res.size(); i ++)
{
//cout << find_leader(res[i]) << " --- " << res[i] << endl;
///if (i == 1)
// exit(0);
if (i % 2 ==0)
even.push_back(res[i]), sz1 += rnk[find_leader(res[i])];
else
odd.push_back(res[i]), sz2 += rnk[find_leader(res[i])];
}
if (sz1 > sz2)
return get_biggest(even, mst);
else
return get_biggest(odd, mst);
}
int hubDistance(int N, int sub)
{
///cout << "hub " << N << " " << sub << endl;
for (int i = 0; i < N; i ++)
for (int j = 0; j < N; j ++)
table[i][j] = 0;
int v = 0, u = -1, best = 0;
for (int i = 1; i < N; i ++)
{
int d = getLocalDistance(i, 0);
if (u == -1 || d > best)
{
best = d;
u = i;
}
}
dist[0] = best;
for (int i = 1; i < N; i ++)
{
if (i != u)
{
int d = getLocalDistance(i, u);
dist[i] = d;
if (d > best)
{
best = d;
v = i;
}
}
}
if (sub == 4)
{
map < int, int > marked;
int ans = 1e9;
for (int i = 0; i < N; i ++)
{
if (i == v || i == u)
continue;
int df = getLocalDistance(v, i), tf = dist[i];
int diff = abs(df - tf);
int lf = (best - diff) / 2 + diff, rf = (best - diff) / 2;
if (df < tf)
swap(lf, rf);
marked[lf] ++;
ans = min(ans, (best - diff) / 2 + diff);
}
int from_left = 1;
for (auto it : marked)
{
int from_right = N - from_left - it.second;
if (max(it.first, best - it.first) == ans)
{
if (max(from_right, max(it.second, from_left)) <= N / 2)
return +ans;
}
from_left += it.second;
}
return -ans;
}
else if (sub == 3 || sub == 5)
{
map < int, vector < int > > marked;
int ans = 1e9;
for (int i = 0; i < N; i ++)
{
if (i == v || i == u)
continue;
int df = getLocalDistance(v, i), tf = dist[i];
path[i] = v;
int diff = abs(df - tf);
int lf = (best - diff) / 2 + diff, rf = (best - diff) / 2;
if (df < tf)
swap(lf, rf);
marked[lf].push_back(i);
ans = min(ans, (best - diff) / 2 + diff);
}
int from_left = 1;
for (auto it : marked)
{
///cout << it.first << " : " << ans << endl;
int from_right = N - from_left - it.second.size();
if (max(it.first, best - it.first) == ans)
{
if (from_left <= N / 2 && from_right <= N / 2)
{
vector < int > st = it.second;
for (int v : st)
{
par[v] = v;
rnk[v] = 1;
}
int maj = -1, cnt = 0;
for (int v : st)
{
if (cnt == 0)
{
///cout << "make majorant " << v << endl;
maj = v;
cnt ++;
}
else
{
int part = (dist[maj] + dist[v] - getLocalDistance(maj, v)) / 2;
///cout << "here " << maj << " " << cnt << " " << part << " " << best - it.first << endl;
if (part != best - it.first)
cnt ++, unite(maj, v);
else
cnt --;
}
}
if (cnt == 0)
return ans;
for (int v : st)
{
if (v == maj)
continue;
int part = (dist[maj] + dist[v] - getLocalDistance(maj, v)) / 2;
if (part != best - it.first)
unite(maj, v);
}
if (rnk[find_leader(maj)] <= N / 2)
return ans;
///cout << "HERE " << N << " " << st.size() << endl;
/**for (int v : st)
for (int u : st)
{
if (v >= u)
continue;
int part = (dist[v] + dist[u] - getLocalDistance(v, u)) / 2;
if (part != best - it.first)
unite(v, u);
}
bool tf = true;
for (int v : st)
{
cout << rnk[find_leader(v)] << " ";
if (rnk[find_leader(v)] > N / 2)
tf = false;
}
cout << endl;
if (tf)
return ans;*/
}
}
from_left += it.second.size();
}
return -ans;
}
else
{
int ans = 1e9;
for (int i = 0; i < N; i ++)
{
if (i == v || i == u)
continue;
int df = getLocalDistance(v, i), tf = dist[i];
int diff = abs(df - tf);
ans = min(ans, (best - diff) / 2 + diff);
}
return ans;
}
}
Compilation message
towns.cpp: In function 'std::vector<int> get_biggest(std::vector<int>, int)':
towns.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i = 0; i < res.size(); i ++)
| ~~^~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:170:44: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
170 | int from_right = N - from_left - it.second.size();
| ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
towns.cpp:176:30: warning: declaration of 'v' shadows a previous local [-Wshadow]
176 | for (int v : st)
| ^
towns.cpp:95:9: note: shadowed declaration is here
95 | int v = 0, u = -1, best = 0;
| ^
towns.cpp:182:30: warning: declaration of 'v' shadows a previous local [-Wshadow]
182 | for (int v : st)
| ^
towns.cpp:95:9: note: shadowed declaration is here
95 | int v = 0, u = -1, best = 0;
| ^
towns.cpp:204:46: warning: declaration of 'v' shadows a previous local [-Wshadow]
204 | for (int v : st)
| ^
towns.cpp:95:9: note: shadowed declaration is here
95 | int v = 0, u = -1, best = 0;
| ^
towns.cpp:242:41: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
242 | from_left += it.second.size();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
340 KB |
Output is correct |
| 2 |
Correct |
9 ms |
400 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
12 ms |
400 KB |
Output is correct |
| 5 |
Correct |
12 ms |
400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
404 KB |
Output is correct |
| 2 |
Correct |
9 ms |
404 KB |
Output is correct |
| 3 |
Correct |
12 ms |
396 KB |
Output is correct |
| 4 |
Correct |
12 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
356 KB |
Output is correct |
| 2 |
Correct |
12 ms |
400 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
12 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
340 KB |
Output is correct |
| 2 |
Correct |
13 ms |
852 KB |
Output is correct |
| 3 |
Correct |
12 ms |
900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
