| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 169753 |
2019-12-22T15:33:18 Z |
CaroLinda |
Towns (IOI15_towns) |
C++14 |
|
24 ms |
1156 KB |
#include <bits/stdc++.h>
#include "towns.h"
#define debug printf
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define ll long long
#define sz size()
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define tiii tuple<int,int,int>
#define mkt make_tuple
const int MAXN = 120 , inf = 1e9+10 ;
using namespace std ;
int n , v , s , t , r ;
int myRadio[MAXN] , pai[MAXN] ;
int d[MAXN][MAXN] ;
stack<int> List, bucket ;
vector<int> comp[MAXN] ;
inline void ask(int i , int j)
{
if( d[i][j] == -1 )
d[i][j] = d[j][i] = getDistance(i,j) ;
}
bool isDiff(int i, int j)
{
ask(i,j) ;
return d[s][i] + d[s][j] - d[i][j] == 2*r;
}
void print(stack<int> a , stack<int> b )
{
debug("Printing stacks\n") ;
while(!a.empty()) debug("%d " , a.top() ) , a.pop() ;
debug("\n") ;
while(!b.empty()) debug("%d " , b.top() ) , b.pop() ;
debug("\n\n") ;
}
int find(int x)
{
if( x == pai[x] ) return x ;
return pai[x] = find(pai[x]);
}
void join(int a, int b)
{
a = find(a) ;
b=find(b) ;
if(a == b) return ;
if( comp[a].sz < comp[b].sz ) swap( a ,b ) ;
for(int i : comp[b])
comp[a].pb(i) ;
comp[b].clear() ;
pai[b] = a ;
}
int hubDistance(int N, int sub)
{
memset(d, -1, sizeof d ) ;
lp(i,0,N) d[i][i] =0 ;
n = N ;
lp(i,0,n) ask(0,i) ;
v = 0 ;
s = max_element( d[v] , d[v]+n ) - d[v] ;
lp(i,0,n) ask(s,i) ;
t = max_element( d[s] , d[s] + n ) - d[s] ;
r = inf ;
lp(i,0,n)
{
myRadio[i] = ( d[v][s] + d[s][i] - d[v][i] ) >> 1 ;
r = min(r, max( myRadio[i] , d[s][t] - myRadio[i] ) ) ;
}
int toLeftS=0 , toRightS=0 , toLeftT=0 , toRightT=0 ;
vector<int> auxS , auxT , toTest ;
lp(i,0,n)
{
if( myRadio[i] < r ) toLeftS ++ ;
else if( myRadio[i] > r ) toRightS ++ ;
else toTest.pb(i) ;
int aux = d[s][t] - myRadio[i] ;
if( aux < r ) toRightT ++ ;
else if( aux > r ) toLeftT ++ ;
else auxT.pb(i) ;
}
toLeftS = max(toLeftS, toRightS ) ;
toLeftT = max(toLeftT, toRightT ) ;
if( sub <= 2 ) return r ;
int R = r ;
if( toLeftS > n/2 )
{
if( toLeftT > n/2 ) return -R ;
r = d[s][t] - r ;
swap(toTest, auxT ) ;
}
lp(i,0,n)
{
pai[i] = i ;
comp[i].clear() ;
comp[i].pb(i) ;
}
lp(i,0,toTest.sz)
lp(j,i+1,toTest.sz )
if( !isDiff(toTest[i], toTest[j] ) )
join( toTest[i] , toTest[j] ) ;
int mx = -1 ;
lp(i,0,n) mx = max( mx, (int)(comp[find(i)].sz) ) ;
if( mx > n/2 ) return -R ;
return R ;
}
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:82:35: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
s = max_element( d[v] , d[v]+n ) - d[v] ;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
towns.cpp:85:37: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
t = max_element( d[s] , d[s] + n ) - d[s] ;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
towns.cpp:5:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
^
towns.cpp:137:3: note: in expansion of macro 'lp'
lp(i,0,toTest.sz)
^~
towns.cpp:5:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
^
towns.cpp:138:4: note: in expansion of macro 'lp'
lp(j,i+1,toTest.sz )
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
376 KB |
Output is correct |
| 2 |
Correct |
17 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
22 ms |
380 KB |
Output is correct |
| 5 |
Correct |
21 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
376 KB |
Output is correct |
| 2 |
Correct |
16 ms |
468 KB |
Output is correct |
| 3 |
Correct |
21 ms |
376 KB |
Output is correct |
| 4 |
Correct |
21 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
376 KB |
Output is correct |
| 2 |
Correct |
24 ms |
1156 KB |
Output is correct |
| 3 |
Correct |
2 ms |
348 KB |
Output is correct |
| 4 |
Correct |
22 ms |
1016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
