| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 591009 |
2022-07-06T17:30:23 Z |
AlperenT |
Towns (IOI15_towns) |
C++17 |
|
19 ms |
888 KB |
#include <bits/stdc++.h>
#include "towns.h"
using namespace std;
const int N = 110, INF = 1e9 + 5;
struct City{
int adist, bdist, acnt, bcnt;
vector<int> childs;
vector<pair<int, int>> childs2;
};
int dist[N][N];
struct DSU{
int par[N], setsize[N];
void reset(){
for(int i = 0; i < N; i++) par[i] = i, setsize[i] = 1;
}
int setfind(int a){
if(par[a] == a) return par[a];
else return par[a] = setfind(par[a]);
}
void setunion(int a, int b){
a = setfind(a), b = setfind(b);
if(a != b){
if(setsize[b] > setsize[a]) swap(a, b);
par[b] = par[a];
setsize[a] += setsize[b];
}
}
};
DSU dsu;
int hubDistance(int n, int sub){
if(sub == 3){
dsu.reset();
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
dist[i][j] = dist[j][i] = getDistance(i, j);
}
}
int A = max_element(dist[0], dist[0] + n) - dist[0];
int B = max_element(dist[A], dist[A] + n) - dist[A];
map<pair<int, int>, vector<pair<int, int>>> mp;
for(int C = 0; C < n; C++){
int xtoc = (dist[A][C] + dist[B][C] - dist[A][B]) / 2;
mp[{dist[A][C] - xtoc, dist[B][C] - xtoc}].push_back({xtoc, C});
}
int mn = INF;
for(auto p : mp) mn = min(mn, max(p.first.first, p.first.second));
vector<City> cities;
for(auto p : mp) cities.push_back({p.first.first, p.first.second, 0, 0, {}, p.second});
int sum = 0;
for(int i = 0; i < cities.size(); i++){
cities[i].acnt = sum;
sum += cities[i].childs2.size();
}
sum = 0;
for(int i = cities.size() - 1; i >= 0; i--){
cities[i].bcnt = sum;
sum += cities[i].childs2.size();
}
vector<City> hubs;
for(auto cty : cities){
if(max(cty.adist, cty.bdist) == mn && cty.acnt <= n / 2 && cty.bcnt <= n / 2){
hubs.push_back(cty);
}
}
// cout << hubs.size() << "\n";
for(auto hub : hubs){
for(int i = 0; i < hub.childs2.size(); i++){
for(int j = i + 1; j < hub.childs2.size(); j++){
if(dist[hub.childs2[i].second][hub.childs2[j].second] != hub.childs2[i].first + hub.childs2[j].first){
dsu.setunion(hub.childs2[i].second, hub.childs2[j].second);
}
}
}
int mx = 0;
// cout << hub.adist << " " << hub.acnt << " " << hub.bdist << " " << hub.bcnt << "\n";
// for(auto p : hub.childs2) cout << p.second << " " << dsu.setsize[dsu.setfind(p.second)] << "\n";
for(auto p : hub.childs2) mx = max(mx, dsu.setsize[dsu.setfind(p.second)]);
if(mx <= n / 2) return mn;
}
return -mn;
}
else{
int dist0[n];
for(int i = 0; i < n; i++) dist0[i] = getDistance(0, i);
int A = max_element(dist0, dist0 + n) - dist0;
int distA[n];
for(int i = 0; i < n; i++) distA[i] = getDistance(A, i);
int B = max_element(distA, distA + n) - distA;
int distB[n];
for(int i = 0; i < n; i++) distB[i] = getDistance(B, i);
map<pair<int, int>, vector<int>> mp;
for(int C = 0; C < n; C++){
int xtoc = (distA[C] + distB[C] - distA[B]) / 2;
mp[{distA[C] - xtoc, distB[C] - xtoc}].push_back(xtoc);
}
int mn = INF;
for(auto p : mp) mn = min(mn, max(p.first.first, p.first.second));
if(sub == 1 || sub == 2) return mn;
else if(sub == 4){
vector<City> cities;
for(auto p : mp) cities.push_back({p.first.first, p.first.second, 0, 0, p.second, {}});
int sum = 0;
for(int i = 0; i < cities.size(); i++){
cities[i].acnt = sum;
sum += cities[i].childs.size();
}
sum = 0;
for(int i = cities.size() - 1; i >= 0; i--){
cities[i].bcnt = sum;
sum += cities[i].childs.size();
}
for(auto cty : cities){
if(max(cty.adist, cty.bdist) == mn && cty.acnt <= n / 2 && cty.bcnt <= n / 2 && cty.childs.size() <= n / 2) return mn;
}
return -mn;
}
else return -1;
}
}
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:53:45: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
53 | int A = max_element(dist[0], dist[0] + n) - dist[0];
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
towns.cpp:55:45: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
55 | int B = max_element(dist[A], dist[A] + n) - dist[A];
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
towns.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<City>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i = 0; i < cities.size(); i++){
| ~~^~~~~~~~~~~~~~~
towns.cpp:78:34: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
78 | sum += cities[i].childs2.size();
| ^
towns.cpp:83:29: warning: conversion from 'std::vector<City>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
83 | for(int i = cities.size() - 1; i >= 0; i--){
| ~~~~~~~~~~~~~~^~~
towns.cpp:86:34: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
86 | sum += cities[i].childs2.size();
| ^
towns.cpp:100:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(int i = 0; i < hub.childs2.size(); i++){
| ~~^~~~~~~~~~~~~~~~~~~~
towns.cpp:101:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int j = i + 1; j < hub.childs2.size(); j++){
| ~~^~~~~~~~~~~~~~~~~~~~
towns.cpp:126:41: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
126 | int A = max_element(dist0, dist0 + n) - dist0;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
towns.cpp:132:41: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
132 | int B = max_element(distA, distA + n) - distA;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
towns.cpp:158:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<City>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | for(int i = 0; i < cities.size(); i++){
| ~~^~~~~~~~~~~~~~~
towns.cpp:161:34: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
161 | sum += cities[i].childs.size();
| ^
towns.cpp:166:30: warning: conversion from 'std::vector<City>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
166 | for(int i = cities.size() - 1; i >= 0; i--){
| ~~~~~~~~~~~~~~^~~
towns.cpp:169:34: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
169 | sum += cities[i].childs.size();
| ^
towns.cpp:173:103: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
173 | if(max(cty.adist, cty.bdist) == mn && cty.acnt <= n / 2 && cty.bcnt <= n / 2 && cty.childs.size() <= n / 2) return mn;
| ~~~~~~~~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
352 KB |
Output is correct |
| 2 |
Correct |
15 ms |
356 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
12 ms |
340 KB |
Output is correct |
| 5 |
Correct |
14 ms |
356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
468 KB |
Output is correct |
| 2 |
Correct |
10 ms |
356 KB |
Output is correct |
| 3 |
Correct |
14 ms |
340 KB |
Output is correct |
| 4 |
Correct |
12 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
404 KB |
Output is correct |
| 2 |
Correct |
15 ms |
852 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
19 ms |
888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
368 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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
