#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int , int> >kinder[300000] , ka;
vector<int>cent , ed;
int sub[300000], vis[300000];
long long a , b , menge , cmp , comp ,numm , kind , vase;
int st , en , mid , mit;
int centroid(int x , int f , int n){
for(int i = 0 ; i < kinder[x].size() ; i++){
kind = kinder[x][i].first;
if(vis[kind] != 2 &&kind != f && sub[kind] * 2 > n){
return centroid(kind , x , n);
}
}
for(int i = 0 ; i < kinder[x].size() ; i++){
ed[kinder[x][i].second] = 1;
}
vis[x] = 2;
return x;
}
int dfs(int x){
vis[x] = 1;
sub[x] = 1;
for(int i = 0 ; i < kinder[x].size() ; i++){
kind = kinder[x][i].first;
if(vis[kind] == 0){
sub[x] += dfs(kind);
}
}
return sub[x];
}
int bis(int x , int y , long long z ,int f , int root){
for(int i = 0 ; i <= y ; i++){
ed[kinder[root][i].second] = 1;
}
st = x ; en = y; mid = y;
while(st <= en){
mit = (st + en)/2;
while(mid > mit){
if(kinder[root][mid].first == f || vis[kinder[root][mid].first] == 2){
mid--;
continue;
}
ed[kinder[root][mid].second] = 0;
mid--;
}
while(mid <= mit){
if(kinder[root][mid].first == f || vis[kinder[root][mid].first] == 2){
mid++;
continue;
}
ed[kinder[root][mid].second] = 1;
mid++;
}
if(mid > mit){
mid--;
}
numm = ask(ed);
if(numm >= z){
en = mit - 1;
}
else{
st = mit + 1;
}
}
for(int i = 0 ; i <= y ; i++){
ed[kinder[root][i].second] = 1;
}
return st;
}
long long suche(int x){
// cout << x << "\n";
dfs(x);
long long nummer = centroid(x ,x , sub[x]);
for(int i = 0 ; i < menge ; i++){
if(vis[i] == 1){
vis[i] = 0;
}
}
// cout << nummer << ' ' << x << "\n";
// cout << kinder[nummer].size() << "\n";
int fater = -1,pl;
for(int i = 0 ; i < kinder[nummer].size() ; i++ ){
if(sub[kinder[nummer][i].first] > sub[nummer] && vis[kinder[nummer][i].first] != 2){
fater = kinder[nummer][i].first;
break;
}
}
// cout << fater << "\n";
cmp = ask(ed);
// cout << cmp - comp << "\n";
if(nummer == x){
// while(true);
if(cmp == comp){
return nummer;
}
else{
comp = cmp;
pl = bis(0 , kinder[nummer].size() - 1 , cmp , fater , nummer );
}
}
else{
if(cmp == comp){
// while(true);
return suche(x);
}
else if(cmp == comp + b - a){
comp = cmp;
// while(true);
return nummer;
}
else{
// while(true);
comp = cmp;
pl = bis(0 , kinder[nummer].size() - 1 , cmp , fater , nummer );
// cout << kinder[nummer].size() << "\n";
}
}
return suche(kinder[nummer][pl].first);
}
void finde(){
cent.clear();
ka.clear();
for(int i = 0 ; i < menge ; i++){
if(vis[i] == 0){
ka.push_back({i , dfs(i)});
}
}
for(int i = 0 ; i < ka.size() ; i++){
cent.push_back(centroid(ka[i].first , ka[i].first , ka[i].second));
// cout << cent[i] << ' ';
}
// cout << "\n";
for(int i = 0 ; i < menge ; i++){
if(vis[i] == 1){
vis[i] = 0;
}
}
ka.clear();
comp = ask(ed);
vase = comp;
if(comp > cmp){
st = 0 ; en = cent.size() - 2; mid = cent.size() - 1;
while(st <= en){
mit = (st + en)/2;
while(mid > mit){
for(int i = 0 ; i < kinder[cent[mid]].size() ; i++){
ed[kinder[cent[mid]][i].second] = 0;
}
mid--;
}
while(mid <= mit){
for(int i = 0 ; i < kinder[cent[mid]].size() ; i++){
ed[kinder[cent[mid]][i].second] = 1;
}
mid++;
}
if(mid > mit){
mid--;
}
numm = ask(ed);
if(numm == comp){
en = mit - 1;
}
else{
st = mit + 1;
}
}
int root , er ,zw;
root = cent[st];
// cout << root << "\n";
cent.clear();
er = bis(0 , kinder[root].size() - 1 , cmp +b -a , -1 , root);
// cout << er << "\n";
if(comp == cmp + b - a){
zw = root;
}
else{
// while(true);
zw = bis(er , kinder[root].size() - 1 , comp , -1 , root);
// cout << zw << ' ' << kinder[root][zw].first << "\n";
// cout << kinder[root][er].first << "\n";
zw = suche(kinder[root][zw].first);
// cout << zw << "\n";
}
er = suche(kinder[root][er].first);
// comp = ask(ed);
// cout << er << "\n";
answer(er , zw);
return;
}
cent.clear();
finde();
}
void find_pair(int N, vector<int> u, vector<int> v, int A, int B) {
a = A;
b = B;
menge = N;
for(int i = 0 ; i < u.size() ; i++){
kinder[u[i]].push_back({v[i] , i});
kinder[v[i]].push_back({u[i] , i});
ed.push_back(0);
}
cmp = ask(ed);
finde();
}
Compilation message
highway.cpp: In function 'int centroid(int, int, int)':
highway.cpp:10: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]
10 | for(int i = 0 ; i < kinder[x].size() ; i++){
| ~~^~~~~~~~~~~~~~~~~~
highway.cpp:16: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]
16 | for(int i = 0 ; i < kinder[x].size() ; i++){
| ~~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'int dfs(int)':
highway.cpp:25: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]
25 | for(int i = 0 ; i < kinder[x].size() ; i++){
| ~~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'long long int suche(int)':
highway.cpp:87: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]
87 | for(int i = 0 ; i < kinder[nummer].size() ; i++ ){
| ~~^~~~~~~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void finde()':
highway.cpp:139: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]
139 | for(int i = 0 ; i < ka.size() ; i++){
| ~~^~~~~~~~~~~
highway.cpp:158:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | for(int i = 0 ; i < kinder[cent[mid]].size() ; i++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:166:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
166 | for(int i = 0 ; i < kinder[cent[mid]].size() ; i++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:215:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
215 | for(int i = 0 ; i < u.size() ; i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7248 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7360 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7360 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7248 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7248 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7248 KB |
Output is correct |
| 7 |
Correct |
4 ms |
7248 KB |
Output is correct |
| 8 |
Correct |
4 ms |
7364 KB |
Output is correct |
| 9 |
Correct |
5 ms |
7240 KB |
Output is correct |
| 10 |
Correct |
4 ms |
7248 KB |
Output is correct |
| 11 |
Correct |
6 ms |
7248 KB |
Output is correct |
| 12 |
Correct |
4 ms |
7248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7376 KB |
Output is correct |
| 2 |
Correct |
16 ms |
7888 KB |
Output is correct |
| 3 |
Correct |
140 ms |
13192 KB |
Output is correct |
| 4 |
Correct |
102 ms |
13188 KB |
Output is correct |
| 5 |
Correct |
136 ms |
13188 KB |
Output is correct |
| 6 |
Incorrect |
138 ms |
13188 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
8528 KB |
Output is correct |
| 2 |
Correct |
27 ms |
9652 KB |
Output is correct |
| 3 |
Correct |
34 ms |
11004 KB |
Output is correct |
| 4 |
Correct |
90 ms |
18496 KB |
Output is correct |
| 5 |
Correct |
101 ms |
18396 KB |
Output is correct |
| 6 |
Correct |
95 ms |
18276 KB |
Output is correct |
| 7 |
Correct |
98 ms |
18276 KB |
Output is correct |
| 8 |
Correct |
117 ms |
18268 KB |
Output is correct |
| 9 |
Correct |
102 ms |
18268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7408 KB |
Output is correct |
| 2 |
Correct |
11 ms |
7932 KB |
Output is correct |
| 3 |
Correct |
90 ms |
11916 KB |
Output is correct |
| 4 |
Correct |
132 ms |
13184 KB |
Output is correct |
| 5 |
Correct |
144 ms |
13216 KB |
Output is correct |
| 6 |
Correct |
117 ms |
13240 KB |
Output is correct |
| 7 |
Correct |
182 ms |
13416 KB |
Output is correct |
| 8 |
Correct |
146 ms |
13400 KB |
Output is correct |
| 9 |
Incorrect |
117 ms |
13188 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3027 ms |
8144 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3042 ms |
8056 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
