#include <bits/stdc++.h>
#include "highway.h"
#define MAX 90010
using namespace std;
typedef pair<int,int> pii;
typedef long long int lli;
int N, A, B;
int prof[MAX];
int paiEdge[MAX];
lli distA;
lli distB;
vector<int> grafo[MAX];
vector<int> indEdge[MAX];
vector<int> distNode[MAX];
vector<pii> searchSpace;
void DFS(int i, int p)
{
distNode[ prof[i] ].push_back( i );
for(int g = 0 ; g < grafo[i].size() ; g++)
{
int prox = grafo[i][g];
int ind = indEdge[i][g];
if(prox == p) continue;
paiEdge[ prox ] = ind;
prof[ prox ] = prof[ i ] + 1;
DFS(prox , i);
}
}
void initDFS()
{
for(int g = 0 ; g <= N ; g++)
distNode[ g ].clear();
}
bool test(int l, int r)
{
vector<int> query(N - 1 , 0);
for(int g = l ; g <= r ; g++)
{
int cur = searchSpace[ g ].second;
query[ cur ] = 1;
}
lli aux = ask( query );
return aux != distA;
}
bool test(int k)
{
vector<int> query(N - 1 , 0);
for(int g = 1 ; g < N ; g++)
if(prof[g] <= k) query[ paiEdge[g] ] = 1;
lli aux = ask( query );
return aux == distB;
}
int find(int root, int d)
{
initDFS(); prof[ root ] = 0;
DFS(root , root);
searchSpace.clear();
for(int g = 0 ; g < distNode[ d ].size() ; g++)
{
int prox = distNode[d][g];
searchSpace.push_back({ prox , paiEdge[ prox ] });
}
int l = 0, r = searchSpace.size() - 1;
while(l < r)
{
int m = (l + r)/2;
if(test(l , m)) r = m;
else l = m + 1;
}
return searchSpace[ l ].first;
}
void find_pair(int n, vector<int> U, vector<int> V, int a, int b)
{
N = n; A = a; B = b;
for(int g = 0 ; g < N - 1 ; g++)
{
int i = U[g];
int j = V[g];
grafo[ i ].push_back( j );
grafo[ j ].push_back( i );
indEdge[ i ].push_back( g );
indEdge[ j ].push_back( g );
}
vector<int> nullVector(N - 1 , 0);
distA = ask( nullVector );
distB = distA/A; distB *= B;
DFS(0 , 0);
int l = 0, r = n - 1;
while(l < r)
{
int m = (l + r)/2;
if(test(m)) r = m;
else l = m + 1;
}
int S = find(0 , r);
int T = find(S , distA/A);
answer(S , T);
}
Compilation message
highway.cpp: In function 'void DFS(int, int)':
highway.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int g = 0 ; g < grafo[i].size() ; g++)
~~^~~~~~~~~~~~~~~~~
highway.cpp: In function 'int find(int, int)':
highway.cpp:83:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int g = 0 ; g < distNode[ d ].size() ; g++)
~~^~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
6648 KB |
Output is correct |
2 |
Correct |
8 ms |
6648 KB |
Output is correct |
3 |
Correct |
8 ms |
6676 KB |
Output is correct |
4 |
Correct |
8 ms |
6648 KB |
Output is correct |
5 |
Correct |
8 ms |
6648 KB |
Output is correct |
6 |
Correct |
8 ms |
6648 KB |
Output is correct |
7 |
Correct |
7 ms |
6676 KB |
Output is correct |
8 |
Correct |
8 ms |
6648 KB |
Output is correct |
9 |
Correct |
7 ms |
6648 KB |
Output is correct |
10 |
Correct |
9 ms |
6672 KB |
Output is correct |
11 |
Correct |
8 ms |
6764 KB |
Output is correct |
12 |
Correct |
7 ms |
6648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
6748 KB |
Output is correct |
2 |
Correct |
31 ms |
7704 KB |
Output is correct |
3 |
Correct |
267 ms |
16200 KB |
Output is correct |
4 |
Correct |
262 ms |
16072 KB |
Output is correct |
5 |
Correct |
305 ms |
16296 KB |
Output is correct |
6 |
Correct |
273 ms |
16008 KB |
Output is correct |
7 |
Correct |
251 ms |
16308 KB |
Output is correct |
8 |
Correct |
276 ms |
16376 KB |
Output is correct |
9 |
Correct |
268 ms |
16428 KB |
Output is correct |
10 |
Correct |
277 ms |
16220 KB |
Output is correct |
11 |
Correct |
291 ms |
17284 KB |
Output is correct |
12 |
Correct |
297 ms |
17940 KB |
Output is correct |
13 |
Correct |
294 ms |
17296 KB |
Output is correct |
14 |
Correct |
295 ms |
17576 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
8360 KB |
Output is correct |
2 |
Correct |
51 ms |
10016 KB |
Output is correct |
3 |
Correct |
69 ms |
11768 KB |
Output is correct |
4 |
Correct |
195 ms |
22344 KB |
Output is correct |
5 |
Correct |
182 ms |
22176 KB |
Output is correct |
6 |
Correct |
190 ms |
22260 KB |
Output is correct |
7 |
Correct |
201 ms |
22184 KB |
Output is correct |
8 |
Correct |
189 ms |
22232 KB |
Output is correct |
9 |
Correct |
195 ms |
22228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
6776 KB |
Output is correct |
2 |
Correct |
31 ms |
7720 KB |
Output is correct |
3 |
Correct |
209 ms |
14124 KB |
Output is correct |
4 |
Correct |
258 ms |
16092 KB |
Output is correct |
5 |
Correct |
259 ms |
15864 KB |
Output is correct |
6 |
Correct |
324 ms |
16200 KB |
Output is correct |
7 |
Correct |
240 ms |
16168 KB |
Output is correct |
8 |
Correct |
282 ms |
16184 KB |
Output is correct |
9 |
Correct |
272 ms |
16252 KB |
Output is correct |
10 |
Correct |
281 ms |
16092 KB |
Output is correct |
11 |
Correct |
302 ms |
17132 KB |
Output is correct |
12 |
Correct |
291 ms |
17824 KB |
Output is correct |
13 |
Correct |
302 ms |
17336 KB |
Output is correct |
14 |
Correct |
298 ms |
17884 KB |
Output is correct |
15 |
Correct |
269 ms |
15984 KB |
Output is correct |
16 |
Correct |
254 ms |
15980 KB |
Output is correct |
17 |
Correct |
289 ms |
17584 KB |
Output is correct |
18 |
Correct |
299 ms |
17864 KB |
Output is correct |
19 |
Correct |
264 ms |
16036 KB |
Output is correct |
20 |
Correct |
297 ms |
18368 KB |
Output is correct |
21 |
Correct |
225 ms |
17340 KB |
Output is correct |
22 |
Correct |
216 ms |
17332 KB |
Output is correct |
23 |
Correct |
240 ms |
16848 KB |
Output is correct |
24 |
Correct |
238 ms |
17308 KB |
Output is correct |
25 |
Correct |
318 ms |
21664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
23 ms |
7416 KB |
Incorrect |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
25 ms |
7384 KB |
Incorrect |
2 |
Halted |
0 ms |
0 KB |
- |