# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
868047 |
2023-10-30T10:08:54 Z |
waldi |
Towns (IOI15_towns) |
C++17 |
|
15 ms |
1116 KB |
#include "towns.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define fi first
#define se second
#define debug(a) cerr << #a << ": " << a << "\n";
using namespace std;
typedef pair<int, int> pii;
int hubDistance(int n, int sub){
int a = 0;
vector<int> od0(n, 0);
FOR(i, 1, n-1){
od0[i] = getDistance(0, i);
if(od0[i] > od0[a]) a = i;
}
int b = 0;
vector<int> oda(n, 0);
REP(i, n) if(i != a){
oda[i] = getDistance(a, i);
if(oda[i] > oda[b]) b = i;
}
int sred = oda[b];
vector<int> odb(n, 0);
REP(i, n) if(i != b) odb[i] = getDistance(b, i);
set<int> secik;
REP(i, n){
int t = (oda[i]+odb[i]-sred)>>1, odla = oda[i]-t;
secik.emplace(odla);
}
int wyn = sred+1, poz = -1;
for(int off : secik){
int maks = 0;
REP(i, n){
int t = (oda[i]+odb[i]-sred)>>1, odla = oda[i]-t;
maks = max(maks, t + abs(off-odla));
}
if(maks < wyn) wyn = maks, poz = off;
}
if(sub <= 2) return wyn;
if(sub == 4){
int lewo = 0, prawo = 0, ja = 0;
REP(i, n){
int t = (oda[i]+odb[i]-sred)>>1;
int odla = oda[i]-t;
if(odla < poz) ++lewo;
if(odla == poz) ++ja;
if(odla > poz) ++prawo;
}
bool zle = 0;
zle |= lewo > n/2;
zle |= prawo > n/2;
zle |= ja > n/2;// wiem to jest jedno poddrzewo
if(zle) wyn = -wyn;
return wyn;
}
return wyn;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
1116 KB |
Output is correct |
2 |
Correct |
9 ms |
860 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
13 ms |
1016 KB |
Output is correct |
5 |
Correct |
12 ms |
856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
968 KB |
Output is correct |
2 |
Correct |
9 ms |
860 KB |
Output is correct |
3 |
Correct |
12 ms |
860 KB |
Output is correct |
4 |
Correct |
12 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
856 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
1116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
856 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
1112 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |