| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1037837 |
2024-07-29T09:03:42 Z |
anton |
Towns (IOI15_towns) |
C++17 |
|
13 ms |
552 KB |
#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
const int MAX_N= 110;
struct Edge{
int origin, dest;
int l;
Edge(){};
Edge(int _or, int _de, int _l){
l = _l;
origin = _or;
dest = _de;
}
};
int distances[MAX_N][MAX_N];
bool queried[MAX_N][MAX_N];
int getDist(int a, int b){
if(a == b){
return 0;
}
if(!queried[a][b]){
distances[a][b] = getDistance(a, b);
distances[b][a] = distances[a][b];
queried[a][b] = true;
queried[b][a] = true;
}
return distances[a][b];
}
int n;
map<int, int> get_pos(int a, int b){
map<int, int> cats;
for(int i = 0; i<n; i++){
cats[((getDist(a, i)-getDist(b, i))+getDist(a, b))/2]++;
}
return cats;
}
int find_pos(pair<int, int> axis, int i){
int a = axis.first, b= axis.second;
return ((getDist(a, i)-getDist(b, i))+getDist(a, b))/2;
}
struct Base{
pii axis;
int rootPos;
Base(pii a, int rp){
axis = a;
rootPos = rp;
}
};
bool belongs(Base b, int i){
return find_pos(b.axis, i)> b.rootPos;
}
struct DSU{
int len;
vector<int> sz, anc;
vector<int> belongs;
vector<vector<int>> rivals;
DSU(int _len){
len= _len;
sz.resize(len, 1);
anc.resize(len);
belongs.resize(len, 0);
rivals.resize(len);
for(int i = 0; i<len; i++){
anc[i]=i;
}
}
void add_rival(int u, int r){
rivals[C(u)].push_back(r);
}
int C(int u){
if(anc[u] == u){
return u;
}
int v = C(anc[u]);
anc[u] = v;
return v;
}
void merge(int a, int b){
a = C(a);
b = C(b);
if(a == b){
return;
}
if(sz[a]<sz[b]){
swap(a, b);
}
anc[b] = a;
sz[a] += sz[b];
if(abs(belongs[b])>0){
belongs[a] = belongs[b];
}
for(auto e: rivals[b]){
rivals[a].push_back(e);
}
}
};
int find_sz_big(pair<int, int> axis, int root_pos){
vector<Base> cur_group = {};
DSU friends(n);
friends.add_rival(axis.first, axis.second);
friends.add_rival(axis.second, axis.first);
int dist = getDist(axis.first, axis.second);
for(int i = 0; i<n; i++){
if(i!= axis.second && i!=axis.first){
if(cur_group.size()== 0 || belongs(cur_group[0], i)){
if(cur_group.size()>0){
friends.merge(cur_group[0].axis.second, i);
}
if(getDist(axis.first, i)>=root_pos){
cur_group.push_back(Base({axis.first, i}, root_pos));
}
else{
cur_group.push_back(Base({axis.second, i}, dist-root_pos));
}
}
else{
friends.add_rival(i, cur_group.back().axis.second);
friends.add_rival(cur_group.back().axis.second, i);
cur_group.pop_back();
}
}
}
if(cur_group.size() == 0){
return 0;
}
Base cand= cur_group.back();
int id = friends.C(cand.axis.second);
friends.belongs[id] = 1;
for(auto e: friends.rivals[id]){
friends.belongs[friends.C(e)] = -1;
}
for(int i = 0; i<n; i++){
int u = friends.C(i);
if(abs(friends.belongs[u])<1){
if(belongs(cand, u)){
friends.belongs[u] = 1;
for(auto e : friends.rivals[u]){
friends.belongs[friends.C(e)] = -1;
}
}
else{
friends.belongs[u] = -1;
}
}
}
int maxSZ = 0;
for(int i = 0; i<n; i++){
if(friends.belongs[friends.C(i)] == 1){
maxSZ ++;
}
}
return maxSZ;
}
int R = 0;
int max_dist = 0;
pair<int, int> find_axis(){
int rec = 0;
int next = 1;
int cur = 0;
for(int i = 0; i<n; i++){
if(getDist(cur, i)>rec){
rec = getDist(cur, i);
next= i;
}
}
rec= 0;
cur= next;
for(int i = 0; i<n; i++){
if(getDist(cur, i)>rec){
rec = getDist(cur, i);
next= i;
}
}
return {cur, next};
}
pair<int, int> axis;
void find_center(){
axis= find_axis();
int i = axis.first, j = axis.second;
int dist_total = getDist(i, j);
auto v = get_pos(i, j);
int pathR = 1e9;
for(auto mid: v){
pathR = min(pathR, max(mid.first,dist_total-mid.first));
}
R = pathR;
max_dist = dist_total;
axis = {i, j};
}
int hubDistance(int N, int sub) {
fill(&queried[0][0], &queried[MAX_N-1][MAX_N], false);
n= N;
find_center();
if(sub == 2){
return R;
}
int min_big_child = 1e9;
if(sub == 4){
auto v = get_pos(axis.first, axis.second);
int left= 0;
int dist_total = getDist(axis.first, axis.second);
for(auto e: v){
int mid = e.second;
int right = n -left-mid;
if(max(e.first, dist_total-e.first) == R){
if(left<=n/2 && right <= n/2 && mid<=n/2){
return R;
}
}
left += e.second;
}
return -R;
}
int left= 0;
for(auto e : get_pos(axis.first, axis.second)){
int mid = e.second;
int right = n -left-mid;
int dist_total = getDist(axis.first, axis.second);
//cout<<e.first<<" "<<e.second<<" "<<left<<" "<<mid<<" "<<right<<endl;
if(max(e.first, dist_total-e.first) == R && (left<=n/2 && right<= n/2)){
int v= find_sz_big(axis, e.first);
min_big_child= min(min_big_child, v);
}
if(min_big_child <= (N/2)){
return R;
}
left+= e.second;
}
if(min_big_child <= (N/2)){
return R;
}
else{
return -R;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
348 KB |
Output is correct |
| 2 |
Correct |
7 ms |
552 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
9 ms |
348 KB |
Output is correct |
| 5 |
Correct |
9 ms |
552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
348 KB |
Output is correct |
| 2 |
Correct |
7 ms |
544 KB |
Output is correct |
| 3 |
Correct |
9 ms |
540 KB |
Output is correct |
| 4 |
Correct |
10 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
344 KB |
Output is correct |
| 2 |
Correct |
13 ms |
548 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
9 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
348 KB |
Output is correct |
| 2 |
Correct |
9 ms |
344 KB |
Output is correct |
| 3 |
Correct |
10 ms |
548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
