#include "highway.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define pb push_back
using namespace std;
int m, n;
vector<int>adj[100000];
vector<int>idx[100000];
int totalA, totalB;
ll largo ;
int centro;
bool vis[100000];
bool banned[130005];
short color[130000];
int pintao[2]; // cuantos pintados de ese color
void reiniciar(){
memset(vis, false, sizeof vis);
}
int hijos(int node, int parent){
int cuantos = 0;
int maxi = 0;
vis[node] = true;
for(int i = 0 ; i < adj[node].size() ; i ++){
if(vis[adj[node][i]] or adj[node][i] == parent or banned[idx[node][i]])continue;
int temp = hijos(adj[node][i], node);
cuantos += temp;
maxi = max(maxi, cuantos);
}
maxi = max(maxi, totalA-cuantos); // OJO
if(maxi <= (totalA+1)/2){
centro = node;
}
return cuantos+1;
}
void colorear(int node, int parent, short cual){
for(int i = 0 ; i < adj[node].size() ; i ++){
if(banned[idx[node][i]] or adj[node][i] == parent)continue;
colorear(adj[node][i], node, cual);
color[idx[node][i]] = cual;
}
}
pair<int, int> distancia(int inicio, int fin1, int fin2){
int dist[100000];
for(int i = 0 ; i <= n ; i ++)dist[i] = INT_MAX;
memset(vis, false, sizeof vis);
queue<int>cola;
dist[inicio] = 0;
vis[inicio] = true;
cola.push(inicio);
while(!cola.empty()){
int cur = cola.front();
cola.pop();
for(int i = 0 ; i < adj[cur].size() ; i ++){
if(!vis[adj[cur][i]]){
vis[adj[cur][i]] = true;
dist[adj[cur][i]] = dist[cur] + 1;
//cout << "distancia a " << adj[cur][i] << dist[adj[cur][i]] << endl;
cola.push(adj[cur][i]);
}
}
}
return {dist[fin1], dist[fin2]};
}
bool canReach(int node, int parent, int dest){
if(node == dest)return true;
for(int i = 0 ; i < adj[node].size() ; i ++){
if(adj[node][i] == parent)continue;
if(canReach(adj[node][i], node, dest))return true;
}
return false;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
m = U.size();
for(int i = 0 ; i < m ; i ++){
adj[U[i]].pb(V[i]);
adj[V[i]].pb(U[i]);
idx[U[i]].pb(i);
idx[V[i]].pb(i);
}
n = N;
totalA = n;
vector<int>w;
for(int i = 0 ; i < m ; i ++)w.pb(0);
ll cuanto = ask(w);
largo = cuanto / A;
memset(banned, false, sizeof banned);
centro = 0;
vector<int>mitad1, mitad2, restantes;
int centroFinal;
while(true){
//hallar nodoCentral (centro)
reiniciar();
hijos(centro, -1);
reiniciar();
pintao[0] = 0;
pintao[1] = 0;
//cout << "centro " << centro << endl;
int guarCentro = centro;
for(int i = 0 ; i < adj[guarCentro].size() ; i ++){
if(banned[idx[guarCentro][i]])continue;
int cuan = hijos(adj[guarCentro][i], guarCentro);
//cout << "adds " << cuan << endl;
if(cuan + pintao[0] <= (totalA+1)/2){
//cout << "pintando " << adj[guarCentro][i] << " " << cuan + pintao[0] << endl;
colorear(adj[guarCentro][i], guarCentro, 0);
color[idx[guarCentro][i]] = 0;
pintao[0] += cuan;
}else{
colorear(adj[guarCentro][i], guarCentro, 1);
color[idx[guarCentro][i]] = 1;
pintao[1] += cuan;
}
}
//cout << "!" << pintao[0] << " " << pintao[1] << endl;
for(int i = 0 ; i < m ; i ++){
//cout << "color " << i << " = " << color[i] << endl;
w[i] = color[i];
}
ll resp = ask(w);
if(resp == (ll)A * largo or resp == (ll)B*largo){ // se dividio por completo.
//cout << "se dividio por completo " << endl;
if(resp == B*largo){
totalA = pintao[1];
totalB = pintao[0];
for(int i = 0 ; i < m ; i ++){
if(w[i] == 0)banned[i] = true;
}
}else{
totalA = pintao[0];
totalB = pintao[1];
for(int i = 0 ; i < m ; i ++){
if(w[i] == 1)banned[i] = true;
}
}
//cout << "quedaron " << totalA << endl;
if(totalA == 1){
for(int i = 0 ; i < m ; i ++){
if(!banned[i]){
answer(U[i], V[i]);
return ;
}
}
}
for(int i = 0 ; i < m ; i ++){
color[i] = 0;
}
}else{ // se dividio parcialmente.
//cout << "se dividio a la mita " << endl;
for(int i = 0 ; i < m ; i ++){
if(!banned[i]){
restantes.pb(i);
if(color[i])mitad1.pb(i);
else mitad2.pb(i);
}
}
centroFinal = guarCentro;
break;
}
centro = guarCentro;
//break;
}
int ansA, ansB;
for(int i = 0 ; i < m ; i ++)banned[i] = true;
for(int i = 0 ; i < mitad1.size() ; i ++)banned[mitad1[i]] = false;
totalA = mitad1.size();
for(int i = 0 ; i < m ; i ++){
color[i] = 0;
}
centro = centroFinal;
//int ip = 0;
while(true){
//hallar nodoCentral (centro)
reiniciar();
hijos(centro, -1);
reiniciar();
pintao[0] = 0;
pintao[1] = 0;
//cout << "centro " << centro << endl;
int guarCentro = centro;
for(int i = 0 ; i < adj[guarCentro].size() ; i ++){
if(banned[idx[guarCentro][i]])continue;
int cuan = hijos(adj[guarCentro][i], guarCentro);
//cout << "adds " << cuan << endl;
if((canReach(adj[guarCentro][i], guarCentro, centroFinal) and (pintao[0] + cuan <= (totalA+1)/2) )or (pintao[1] + cuan > (totalA+1)/2)){
colorear(adj[guarCentro][i], guarCentro, 0);
color[idx[guarCentro][i]] = 0;
pintao[0] += cuan;
}else{
colorear(adj[guarCentro][i], guarCentro, 1);
color[idx[guarCentro][i]] = 1;
pintao[1] += cuan;
}
}
//cout << "!" << pintao[0] << " " << pintao[1] << endl;
for(int i = 0 ; i < m ; i ++){
//cout << "color " << i << " = " << color[i] << endl;
w[i] = color[i];
}
ll resp = ask(w);
if(resp > (ll)A*largo){ // le dio
totalA = pintao[1];
totalB = pintao[0];
for(int i = 0 ; i < m ; i ++){
if(w[i] == 0)banned[i] = true;
}
}else{
totalA = pintao[0];
totalB = pintao[1];
for(int i = 0 ; i < m ; i ++){
if(w[i] == 1)banned[i] = true;
}
}
//cout << "quedaron " << totalA << endl;
if(totalA == 1){
for(int i = 0 ; i < m ; i ++){
if(!banned[i]){
//cout << "opciones " << U[i] << " " << V[i] << endl;
pair<int, int> distancias = distancia(centroFinal, U[i], V[i]);
if(distancias.ff > distancias.ss)ansA = U[i];
else ansA=V[i];
break;
}
}
break;
}
for(int i = 0 ; i < m ; i ++){
color[i] = 0;
}
centro = guarCentro;
}
//return ;
for(int i = 0 ; i < m ; i ++)banned[i] = true;
for(int i = 0 ; i < mitad2.size() ; i ++)banned[mitad2[i]] = false;
totalA = mitad2.size();
for(int i = 0 ; i < m ; i ++){
color[i] = 0;
}
centro = centroFinal;
while(true){
//hallar nodoCentral (centro)
reiniciar();
hijos(centro, -1);
reiniciar();
pintao[0] = 0;
pintao[1] = 0;
//cout << "centro " << centro << endl;
int guarCentro = centro;
for(int i = 0 ; i < adj[guarCentro].size() ; i ++){
if(banned[idx[guarCentro][i]])continue;
int cuan = hijos(adj[guarCentro][i], guarCentro);
////////cout << "adds " << cuan << endl;
if(((canReach(adj[guarCentro][i], guarCentro, centroFinal) and (pintao[0] + cuan <= (totalA+1)/2))) or (pintao[1] + cuan > (totalA+1)/2)){
colorear(adj[guarCentro][i], guarCentro, 0);
color[idx[guarCentro][i]] = 0;
pintao[0] += cuan;
}else{
colorear(adj[guarCentro][i], guarCentro, 1);
color[idx[guarCentro][i]] = 1;
pintao[1] += cuan;
}
}
//cout << "!" << pintao[0] << " " << pintao[1] << endl;
for(int i = 0 ; i < m ; i ++){
//cout << "color " << i << " = " << color[i] << endl;
w[i] = color[i];
}
ll resp = ask(w);
if(resp > (ll)A*largo){ // le dio
totalA = pintao[1];
totalB = pintao[0];
for(int i = 0 ; i < m ; i ++){
if(w[i] == 0)banned[i] = true;
}
}else{
totalA = pintao[0];
totalB = pintao[1];
for(int i = 0 ; i < m ; i ++){
if(w[i] == 1)banned[i] = true;
}
}
////cout << "quedaron " << totalA << endl;
if(totalA == 1){
for(int i = 0 ; i < m ; i ++){
if(!banned[i]){
//cout << "opciones " << U[i] << " " << V[i] << endl;
pair<int, int> distancias = distancia(centroFinal, U[i], V[i]);
if(distancias.ff > distancias.ss)ansB = U[i];
else ansB=V[i];
break;
}
}
break;
}
for(int i = 0 ; i < m ; i ++){
color[i] = 0;
}
centro = guarCentro;
}
////cout << ansA << " " << ansB << endl;
//asw(w);
answer(ansA, ansB);
}
Compilation message
highway.cpp: In function 'int hijos(int, int)':
highway.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int i = 0 ; i < adj[node].size() ; i ++){
| ~~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void colorear(int, int, short int)':
highway.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int i = 0 ; i < adj[node].size() ; i ++){
| ~~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'std::pair<int, int> distancia(int, int, int)':
highway.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i = 0 ; i < adj[cur].size() ; i ++){
| ~~^~~~~~~~~~~~~~~~~
highway.cpp: In function 'bool canReach(int, int, int)':
highway.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i = 0 ; i < adj[node].size() ; i ++){
| ~~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:108:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i = 0 ; i < adj[guarCentro].size() ; i ++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:179:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
179 | for(int i = 0 ; i < mitad1.size() ; i ++)banned[mitad1[i]] = false;
| ~~^~~~~~~~~~~~~~~
highway.cpp:195:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
195 | for(int i = 0 ; i < adj[guarCentro].size() ; i ++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:256:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
256 | for(int i = 0 ; i < mitad2.size() ; i ++)banned[mitad2[i]] = false;
| ~~^~~~~~~~~~~~~~~
highway.cpp:271:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
271 | for(int i = 0 ; i < adj[guarCentro].size() ; i ++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:330:9: warning: 'ansA' may be used uninitialized in this function [-Wmaybe-uninitialized]
330 | answer(ansA, ansB);
| ~~~~~~^~~~~~~~~~~~
highway.cpp:330:9: warning: 'ansB' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
5200 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
5200 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
6868 KB |
Output is correct |
| 2 |
Correct |
27 ms |
8564 KB |
Output is correct |
| 3 |
Correct |
28 ms |
10096 KB |
Output is correct |
| 4 |
Correct |
108 ms |
20980 KB |
Output is correct |
| 5 |
Correct |
89 ms |
19964 KB |
Output is correct |
| 6 |
Correct |
125 ms |
20972 KB |
Output is correct |
| 7 |
Correct |
91 ms |
19964 KB |
Output is correct |
| 8 |
Correct |
140 ms |
20972 KB |
Output is correct |
| 9 |
Correct |
110 ms |
20396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
5200 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
190 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
171 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
