#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ll long long
#define bug(x) cout << #x << " " << x << endl;
const int maxn = 1e5 + 10;
vector<pii> edges;
vector<int> adj[maxn], pai( maxn ), dist( maxn ), arestas;
pii dfs( int cur, int last ){
pii resp( 0, cur );
pai[cur] = last;
for( auto viz : adj[cur] ) if( viz != last ){
auto [d, id] = dfs( viz, cur );
resp = max( resp, pii( d + 1, id ) );
}
return resp;
}
void dfsInit( int cur, int last ){
pai[cur] = last;
for( int viz : adj[cur] ) if( viz != last ){
dist[viz] = dist[cur] + 1;
dfsInit( viz, cur );
}
}
void marca( int k ){
for( int i = 0; i < edges.size(); i++ ){
auto [a, b] = edges[i];
arestas[i] = (int)(max(dist[a], dist[b]) <= k );
// bug(i);
// bug(arestas[i]);
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
int m = U.size();
int n = N;
for( int i = 0; i < m; i++ ){
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
edges.push_back({ U[i], V[i] });
}
// int p1 = dfs( 0, 0 ).second;
// auto [diam, p2] = dfs( p1, p1 );
// for( int x = 0; x < diam/2; x++ ) p2 = pai[p2];
dfsInit( 0, 0 );
arestas.resize(m);
ll distancia = ask(arestas)/A;
// bug(distancia);
int l = 0, r = n - 1;
while( l < r ){
int mid = ( l + r )/2;
marca( mid );
ll aux = ask( arestas );
if( aux == distancia*B ) r = mid;
else l = mid + 1;
}
int nivel_a = r;
// bug(nivel_a);
marca( n - 1 );
vector<int> ids;
for( int i = 0; i < edges.size(); i++ ){
auto [a, b] = edges[i];
if( max( dist[a], dist[b] ) == nivel_a ) ids.push_back(i);
}
l = 0, r = ids.size() - 1;
while( l < r ){
int mid = ( l + r )/2;
for( int i = 0; i < ids.size(); i++ ) arestas[ids[i]] = (int)(!( l <= i && i <= mid ));
if( ask( arestas ) < distancia*B ) r = mid;
else l = mid + 1;
}
auto [x, y] = edges[ids[r]];
int a = (( dist[x] > dist[y]) ? x : y );
answer( 0, a );
//
// vector<bool> ancestral(N);
// int aux = a;
// while( true ){
// ancestral[aux] = true;
// if( aux == pai[aux] ) break;
// aux = pai[aux];
// }
//
// l = max( 0LL, nivel_a - distancia ), r = nivel_a;
//
// while( l < r ){
// int mid = ( l + r )/2;
// marca( mid );
// if( ask( arestas ) == distancia*B - 1LL*( nivel_a - mid )*(B - A)) r = mid;
// else l = mid + 1;
// }
//
// int nivel_b = r;
//
// if( nivel_b == nivel_a - distancia ){
// int b = a;
// for( int i = 0; i < distancia; i++ ) b = pai[b];
// answer( a, b );
// }
// else{
// ids.clear();
// for( int i = 0; i < edges.size(); i++ ){
// auto [a, b] = edges[i];
// if( !(ancestral[a] && ancestral[b] ) && max( dist[a], dist[b] ) == nivel_b ) ids.push_back(i);
// }
//
// marca( n - 1 );
// l = 0, r = ids.size();
// while( l < r ){
// int mid = ( l + r )/2;
// for( int i = 0; i < ids.size(); i++ ) arestas[ids[i]] = (int)(!( l <= i && i <= mid ));
// if( ask( arestas ) < distancia*B ) r = mid;
// else l = mid + 1;
// }
//
// int b = (( dist[edges[ids[r]].first] > dist[edges[ids[r]].second]) ?edges[ids[r]].first : edges[ids[r]].second );
// answer( a, b );
// }
}
Compilation message
highway.cpp: In function 'void marca(int)':
highway.cpp:31: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]
31 | for( int i = 0; i < edges.size(); i++ ){
| ~~^~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:72: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]
72 | for( int i = 0; i < edges.size(); i++ ){
| ~~^~~~~~~~~~~~~~
highway.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for( int i = 0; i < ids.size(); i++ ) arestas[ids[i]] = (int)(!( l <= i && i <= mid ));
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3416 KB |
Output is correct |
| 2 |
Correct |
1 ms |
3416 KB |
Output is correct |
| 3 |
Correct |
1 ms |
3416 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3416 KB |
Output is correct |
| 5 |
Correct |
1 ms |
3416 KB |
Output is correct |
| 6 |
Correct |
1 ms |
3416 KB |
Output is correct |
| 7 |
Correct |
2 ms |
3416 KB |
Output is correct |
| 8 |
Correct |
2 ms |
3416 KB |
Output is correct |
| 9 |
Correct |
3 ms |
3416 KB |
Output is correct |
| 10 |
Correct |
1 ms |
3416 KB |
Output is correct |
| 11 |
Correct |
1 ms |
3416 KB |
Output is correct |
| 12 |
Correct |
1 ms |
3596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3416 KB |
Output is correct |
| 2 |
Correct |
8 ms |
4184 KB |
Output is correct |
| 3 |
Correct |
73 ms |
9072 KB |
Output is correct |
| 4 |
Correct |
83 ms |
9664 KB |
Output is correct |
| 5 |
Correct |
79 ms |
9076 KB |
Output is correct |
| 6 |
Correct |
79 ms |
9196 KB |
Output is correct |
| 7 |
Correct |
76 ms |
9012 KB |
Output is correct |
| 8 |
Correct |
78 ms |
9192 KB |
Output is correct |
| 9 |
Correct |
76 ms |
9012 KB |
Output is correct |
| 10 |
Correct |
72 ms |
9064 KB |
Output is correct |
| 11 |
Correct |
89 ms |
9876 KB |
Output is correct |
| 12 |
Correct |
81 ms |
10328 KB |
Output is correct |
| 13 |
Correct |
80 ms |
10452 KB |
Output is correct |
| 14 |
Correct |
73 ms |
9560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
4440 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3416 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
247 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
223 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
