| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 103602 |
2019-03-31T20:17:56 Z |
Lawliet |
Towns (IOI15_towns) |
C++14 |
|
22 ms |
1264 KB |
#include <bits/stdc++.h>
#include "towns.h"
#define MAX 120
#define OO 1000000010
#define debug //printf
using namespace std;
int n;
int radius;
int diameter;
int qnt_hubs;
int d1, d2, d;
int cnt[5][5];
int dist[MAX][MAX];
vector<int> difference;
vector<int> acumulated;
/*int getDistance(int i, int j)
{
printf("DIST %d e %d\n",i,j);
int a;
scanf("%d",&a);
return a;
}*/
int get_all(int i)
{
for(int g = 0 ; g < n ; g++)
if(dist[g][i] == -1)
dist[g][i] = dist[i][g] = getDistance(g , i);
}
int get_farthest(int i)
{
int ans = i;
for(int g = 0 ; g < n ; g++)
if(dist[i][g] > dist[i][ans]) ans = g;
return ans;
}
int divided_segment(int i, int j, int x)
{
int aux = (dist[j][i] - dist[j][x] + dist[i][x])/2;
return aux;
}
void get_radius()
{
get_all(0);
d1 = get_farthest(0);
get_all(d1);
d2 = get_farthest(d1);
int divided = divided_segment(0 , d1 , d2); //onde o d2 cai nesse segmento inicial [0,d1]
int segment = dist[0][d1]; //tamanho do segmento inicial inteiro
diameter = dist[d1][d2]; //diametro da arvore
for(int g = 0 ; g < n ; g++)
{
int cur = divided_segment(0 , d1 , g);
if(cur < divided) continue;
int r1 = segment - cur;
int r2 = diameter - r1;
int aux = max(r1 , r2);
if(aux < radius) d = r1;
radius = min(radius , aux);
}
if(diameter%2 == 0 && diameter/2 == d) return;
for(int g = 0 ; g < n ; g++)
{
int cur = divided_segment(0 , d1 , g); //distancia do 0 ate onde o g cai no segmento
if(cur == diameter - d) qnt_hubs = 2;
}
}
bool is_equal(int i, int j, int k)
{
int div1 = divided_segment(d1 , 0 , i);
int div2 = divided_segment(d1 , 0 , j);
//printf("div1 = %d div2 = %d\n",div1,div2);
if(div1 == k && div2 == k)
{
if(dist[i][j] == -1)
dist[i][j] = dist[j][i] = getDistance(i , j);
if(divided_segment(d1 , j , i) == k) return false;
return true;
}
if(div1 >= k && div2 <= k) return false;
if(div1 <= k && div2 >= k) return false;
return true;
}
void add(int val, int c, int id)
{
if(val > c) cnt[id][1]++;
if(val < c) cnt[id][0]++;
}
bool is_balanced()
{
int k;
for(int g = 0 ; g < n ; g++)
{
int l = divided_segment(d1 , 0 , g);
add(l , d , 0);
add(l , diameter - d , 1);
}
debug("iniciais 0 d1 = %d d2 = %d\n",d1,d2);
debug("qnt = %d d = %d\n",qnt_hubs,d);
bool aux[] = {true , (qnt_hubs == 2)};
for(int g = 0 ; g < 2 ; g++)
debug("%d %d\n",cnt[g][0],cnt[g][1]);
for(int g = 0 ; g < 2 ; g++)
for(int h = 0 ; h < 2 ; h++)
aux[g] = aux[g] && (cnt[g][h] <= n/2);
debug("aux %d %d\n",aux[0],aux[1]);
if(!aux[0] && !aux[1]) return false;
if(!aux[0]) k = diameter - d;
else k = d;
debug("k = %d\n",k);
difference.push_back(0);
for(int g = 1 ; g < n ; g++)
{
bool equal = is_equal(difference.back() , g , k);
debug("------------- g = %d %d\n",g,difference.back());
if(equal) acumulated.push_back(difference.back());
else
{
difference.push_back(g);
if(!acumulated.empty())
{
difference.push_back(acumulated.back());
acumulated.pop_back();
}
}
for(int k = 0 ; k < difference.size() ; k++) debug("%d ",difference[k]);
debug("\n");
for(int k = 0 ; k < acumulated.size() ; k++) debug("%d ",acumulated[k]);
debug("\n");
}
int majoritary = difference.back();
debug("majoritary = %d\n",majoritary);
while( difference.size() > 1)
{
if(is_equal(majoritary , difference.back() , k)) difference.pop_back();
else if(acumulated.empty()) return true;
else acumulated.pop_back();
difference.pop_back();
debug("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX\n");
for(int k = 0 ; k < difference.size() ; k++) debug("%d ",difference[k]);
debug("\n");
for(int k = 0 ; k < acumulated.size() ; k++) debug("%d ",acumulated[k]);
debug("\n");
}
if(difference.size() == 1)
{
if(is_equal(difference.back() , majoritary , k)) acumulated.push_back(majoritary);
else if(acumulated.empty()) return true;
else acumulated.pop_back();
}
return acumulated.empty();
}
void init()
{
memset(dist , -1 , sizeof(dist));
memset(cnt , 0 , sizeof(cnt));
for(int g = 0 ; g < MAX ; g++) dist[g][g] = 0;
radius = OO;
qnt_hubs = 1;
difference.clear();
acumulated.clear();
}
int hubDistance(int N, int sub)
{
n = N;
init();
get_radius();
if(is_balanced()) return radius;
return -radius;
}
/*int main()
{
scanf("%d",&n);
printf("%d\n",hubDistance(n, 0));
}*/
Compilation message
towns.cpp: In function 'int get_all(int)':
towns.cpp:37:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
towns.cpp: In function 'bool is_balanced()':
towns.cpp:135:41: warning: left operand of comma operator has no effect [-Wunused-value]
debug("iniciais 0 d1 = %d d2 = %d\n",d1,d2);
^~
towns.cpp:135:44: warning: right operand of comma operator has no effect [-Wunused-value]
debug("iniciais 0 d1 = %d d2 = %d\n",d1,d2);
^~
towns.cpp:137:28: warning: left operand of comma operator has no effect [-Wunused-value]
debug("qnt = %d d = %d\n",qnt_hubs,d);
^~~~~~~~
towns.cpp:137:37: warning: right operand of comma operator has no effect [-Wunused-value]
debug("qnt = %d d = %d\n",qnt_hubs,d);
^
towns.cpp:142:28: warning: left operand of comma operator has no effect [-Wunused-value]
debug("%d %d\n",cnt[g][0],cnt[g][1]);
^
towns.cpp:142:28: warning: right operand of comma operator has no effect [-Wunused-value]
debug("%d %d\n",cnt[g][0],cnt[g][1]);
~~~~~~~~^
towns.cpp:148:29: warning: left operand of comma operator has no effect [-Wunused-value]
debug("aux %d %d\n",aux[0],aux[1]);
^
towns.cpp:148:29: warning: right operand of comma operator has no effect [-Wunused-value]
debug("aux %d %d\n",aux[0],aux[1]);
~~~~~^
towns.cpp:155:19: warning: left operand of comma operator has no effect [-Wunused-value]
debug("k = %d\n",k);
^
towns.cpp:163:39: warning: left operand of comma operator has no effect [-Wunused-value]
debug("------------- g = %d %d\n",g,difference.back());
^
towns.cpp:163:57: warning: right operand of comma operator has no effect [-Wunused-value]
debug("------------- g = %d %d\n",g,difference.back());
^
towns.cpp:178:11: warning: declaration of 'k' shadows a previous local [-Wshadow]
for(int k = 0 ; k < difference.size() ; k++) debug("%d ",difference[k]);
^
towns.cpp:125:6: note: shadowed declaration is here
int k;
^
towns.cpp:178:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k = 0 ; k < difference.size() ; k++) debug("%d ",difference[k]);
~~^~~~~~~~~~~~~~~~~~~
towns.cpp:178:72: warning: left operand of comma operator has no effect [-Wunused-value]
for(int k = 0 ; k < difference.size() ; k++) debug("%d ",difference[k]);
^
towns.cpp:179:14: warning: statement has no effect [-Wunused-value]
debug("\n");
^
towns.cpp:180:11: warning: declaration of 'k' shadows a previous local [-Wshadow]
for(int k = 0 ; k < acumulated.size() ; k++) debug("%d ",acumulated[k]);
^
towns.cpp:125:6: note: shadowed declaration is here
int k;
^
towns.cpp:180:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k = 0 ; k < acumulated.size() ; k++) debug("%d ",acumulated[k]);
~~^~~~~~~~~~~~~~~~~~~
towns.cpp:180:72: warning: left operand of comma operator has no effect [-Wunused-value]
for(int k = 0 ; k < acumulated.size() ; k++) debug("%d ",acumulated[k]);
^
towns.cpp:181:14: warning: statement has no effect [-Wunused-value]
debug("\n");
^
towns.cpp:186:28: warning: left operand of comma operator has no effect [-Wunused-value]
debug("majoritary = %d\n",majoritary);
^~~~~~~~~~
towns.cpp:196:70: warning: statement has no effect [-Wunused-value]
debug("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX\n");
^
towns.cpp:198:11: warning: declaration of 'k' shadows a previous local [-Wshadow]
for(int k = 0 ; k < difference.size() ; k++) debug("%d ",difference[k]);
^
towns.cpp:125:6: note: shadowed declaration is here
int k;
^
towns.cpp:198:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k = 0 ; k < difference.size() ; k++) debug("%d ",difference[k]);
~~^~~~~~~~~~~~~~~~~~~
towns.cpp:198:72: warning: left operand of comma operator has no effect [-Wunused-value]
for(int k = 0 ; k < difference.size() ; k++) debug("%d ",difference[k]);
^
towns.cpp:199:14: warning: statement has no effect [-Wunused-value]
debug("\n");
^
towns.cpp:200:11: warning: declaration of 'k' shadows a previous local [-Wshadow]
for(int k = 0 ; k < acumulated.size() ; k++) debug("%d ",acumulated[k]);
^
towns.cpp:125:6: note: shadowed declaration is here
int k;
^
towns.cpp:200:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k = 0 ; k < acumulated.size() ; k++) debug("%d ",acumulated[k]);
~~^~~~~~~~~~~~~~~~~~~
towns.cpp:200:72: warning: left operand of comma operator has no effect [-Wunused-value]
for(int k = 0 ; k < acumulated.size() ; k++) debug("%d ",acumulated[k]);
^
towns.cpp:201:14: warning: statement has no effect [-Wunused-value]
debug("\n");
^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:229:28: warning: unused parameter 'sub' [-Wunused-parameter]
int hubDistance(int N, int sub)
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
17 ms |
896 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
20 ms |
1152 KB |
Output is correct |
| 5 |
Correct |
19 ms |
896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
17 ms |
936 KB |
Output is correct |
| 3 |
Correct |
19 ms |
1060 KB |
Output is correct |
| 4 |
Correct |
22 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
1264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
