#include<bits/stdc++.h>
#include "highway.h"
#define mp make_pair
#define pb push_back
using namespace std;
using pii = pair < int, int >;
vector < vector < pii > > to;
vector < pii > edg, ans;
vector<int> w;
int n, m, A, B;
long long L;
void bfs( int start, int startParent){
ans.clear();
queue < pii > q;
q.push( mp( start, startParent ) );
while( !q.empty() ){
int sz = q.size();
while(sz--){
pii u = q.front();
q.pop();
for( pii v : to[u.first] ){
if( v.first == u.second ) continue;
q.push( mp( v.first, u.first ) );
ans.push_back( mp( v.second, v.first) );
}
}
}
}
int findEnd( int start, int startParent ){
bfs( start, startParent );
fill( w.begin(), w.end(), 0 );
L = ask( w );
/*
cerr << "############\n";
cerr << "start : "<< start << ' ' << startParent << endl;
for(int i = 0 ; i < ans.size() ; i++){
cerr << ans[i].second << ' ' << ans[i].first << endl;
}*/
if( ans.empty() ) return start;
// cerr << L << endl;
long long now;
int l = 0, r = ans.size()-1;
while( l+1 < r ){
int mid = (l+r)>>1;
fill( w.begin(), w.end(), 0 );
for(int i = mid ; i <= r ; i++){
w[ans[i].first] = 1;
}
now = ask( w );
// cerr << l << ' ' << r << " : " << mid << ' ' << now << endl;
if( now > L ) l = mid;
else r = mid-1;
}
// cerr << l << ' ' << r << endl;
if( l != r ){
fill( w.begin(), w.end(), 0 );
w[ ans[l].first ] = 1;
now = ask( w );
if( now > L ) return ans[l].second;
fill( w.begin(), w.end(), 0 );
w[ ans[l+1].first ] = 1;
now = ask( w );
if( now > L ) return ans[l+1].second;
return start;
}
fill( w.begin(), w.end(), 0 );
w[ ans[l].first ] = 1;
now = ask( w );
if( now > L ) return ans[l].second;
return start;
}
int findEdge( int start ){
bfs( start, -1 );
fill( w.begin(), w.end(), 0 );
L = ask( w );
long long now;
int l = 0, r = ans.size()-1;
while( l+1 < r ){
int mid = (l+r)>>1;
fill( w.begin(), w.end(), 0 );
for(int i = mid ; i <= r ; i++){
w[ans[i].first] = 1;
}
now = ask( w );
// cerr << l << ' ' << r << " : " << mid << ' ' << now << endl;
if( now > L ) l = mid;
else r = mid-1;
}
if( l != r ){
fill( w.begin(), w.end(), 0 );
w[ ans[l].first ] = 1;
now = ask( w );
if( now > L ) return ans[l].first;
fill( w.begin(), w.end(), 0 );
w[ ans[l+1].first ] = 1;
now = ask( w );
if( now > L ) return ans[l+1].first;
return start;
}
return ans[l].first;
}
void find_pair(int N, vector<int> U, vector<int> V, int _A, int _B) {
n = N; A = _A; B = _B; m = U.size();
w.resize(m);
to.resize(n+1);
for(int i = 0 ; i < m ; i++){
to[ U[i] ].pb( mp( V[i], i ) );
to[ V[i] ].pb( mp( U[i], i ) );
edg.push_back( mp( V[i], U[i] ) );
}
int e = findEdge( 1 );
// cerr << "### " << edg[e].first << ' ' << edg[e].second << endl;
int s = findEnd( edg[e].first, edg[e].second );
int t = findEnd( edg[e].second, edg[e].first );
cerr << s << ' ' << t << endl;
answer( s, t );
}
/*
4 3 1 3 1 3
0 1
0 2
0 3
10 9 1 5 2 9
0 1
0 2
2 9
1 3
1 4
1 5
3 6
4 7
4 8
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
1288 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
865 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
890 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
