#include "highway.h"
#include "bits/stdc++.h"
using namespace std;
#define MAX_N 90004
int n;
vector <pair <int ,int>> adj[MAX_N];
vector <pair <int ,int>> edges;
int depth[MAX_N];
vector <int> atdep[MAX_N];
void dfs(int u ,int p ,int d=1){
depth[u] = d;
for(auto v : adj[u]) if(v.first != p){
atdep[d].push_back(v.second);
dfs(v.first ,u ,d+1);
}
}
int solve(int u ,int v ,int dist){
memset(depth ,0 ,sizeof depth);
for(int i=0; i<MAX_N; i++)
atdep[i].clear();
dfs(u ,v);
int st = 1 ,en = (*max_element(depth ,depth+n))-1 ,mid;
while(st <= en){
mid = (st+en)>>1;
vector <int> w(n-1 ,0);
for(int i : atdep[mid])
w[i] = 1;
if(ask(w) != dist)
st = mid+1;
else
en = mid-1;
}
vector <int>&eds = atdep[--st];
st = 0 ,en = eds.size()-1 ,mid;
while(st < en){
mid = (st+en)>>1;
vector <int> w(n-1 ,0);
for(int i=st; i<=mid; i++)
w[eds[i]] = 1;
if(ask(w) != dist)
en = mid;
else
st = mid+1;
}
if(en == -1)
return u;
u = edges[eds[en]].first ,v = edges[eds[en]].second;
return depth[u] > depth[v] ? u : v;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n = N;
assert(U.size() == N-1);
for(int i=0; i<N-1; i++)
adj[U[i]].push_back({V[i] ,i}),
adj[V[i]].push_back({U[i] ,i}),
edges.push_back({U[i] ,V[i]});
int dist = ask(vector<int>(n-1 ,0));
int st = 0 ,en = n-1 ,mid;
while(st < en){
mid = (st+en)>>1;
vector <int> w(n-1 ,0);
for(int i=st; i<=mid; i++)
w[i] = 1;
if(ask(w) != dist)
en = mid;
else
st = mid+1;
}
int s = solve(U[en] ,V[en] ,dist);
int t = solve(V[en] ,U[en] ,dist);
answer(s ,t);
}
Compilation message
highway.cpp: In function 'int solve(int, int, int)':
highway.cpp:41:35: warning: right operand of comma operator has no effect [-Wunused-value]
st = 0 ,en = eds.size()-1 ,mid;
^
In file included from /usr/include/c++/7/cassert:44:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
from highway.cpp:2:
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:61:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(U.size() == N-1);
~~~~~~~~~^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4812 KB |
Output is correct |
2 |
Correct |
6 ms |
4812 KB |
Output is correct |
3 |
Correct |
6 ms |
4856 KB |
Output is correct |
4 |
Correct |
6 ms |
4812 KB |
Output is correct |
5 |
Correct |
6 ms |
4896 KB |
Output is correct |
6 |
Correct |
6 ms |
4808 KB |
Output is correct |
7 |
Correct |
7 ms |
4856 KB |
Output is correct |
8 |
Correct |
6 ms |
4808 KB |
Output is correct |
9 |
Correct |
6 ms |
4808 KB |
Output is correct |
10 |
Correct |
6 ms |
4856 KB |
Output is correct |
11 |
Correct |
6 ms |
4900 KB |
Output is correct |
12 |
Correct |
6 ms |
4884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4948 KB |
Output is correct |
2 |
Correct |
47 ms |
5604 KB |
Output is correct |
3 |
Correct |
182 ms |
11320 KB |
Output is correct |
4 |
Correct |
205 ms |
11396 KB |
Output is correct |
5 |
Correct |
196 ms |
11400 KB |
Output is correct |
6 |
Correct |
191 ms |
11408 KB |
Output is correct |
7 |
Correct |
186 ms |
11440 KB |
Output is correct |
8 |
Correct |
194 ms |
11396 KB |
Output is correct |
9 |
Correct |
190 ms |
11320 KB |
Output is correct |
10 |
Correct |
187 ms |
11404 KB |
Output is correct |
11 |
Correct |
198 ms |
12568 KB |
Output is correct |
12 |
Correct |
212 ms |
13828 KB |
Output is correct |
13 |
Correct |
197 ms |
13124 KB |
Output is correct |
14 |
Incorrect |
182 ms |
13192 KB |
Output is incorrect: {s, t} is wrong. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
6520 KB |
Output is correct |
2 |
Correct |
46 ms |
8080 KB |
Output is correct |
3 |
Correct |
59 ms |
9888 KB |
Output is correct |
4 |
Correct |
169 ms |
17144 KB |
Output is correct |
5 |
Correct |
164 ms |
17220 KB |
Output is correct |
6 |
Correct |
176 ms |
19108 KB |
Output is correct |
7 |
Correct |
179 ms |
20860 KB |
Output is correct |
8 |
Correct |
170 ms |
18016 KB |
Output is correct |
9 |
Incorrect |
175 ms |
21468 KB |
Output is incorrect: {s, t} is wrong. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4952 KB |
Output is correct |
2 |
Correct |
27 ms |
5572 KB |
Output is correct |
3 |
Correct |
149 ms |
9872 KB |
Output is correct |
4 |
Correct |
197 ms |
11232 KB |
Output is correct |
5 |
Correct |
186 ms |
11320 KB |
Output is correct |
6 |
Correct |
192 ms |
11288 KB |
Output is correct |
7 |
Correct |
193 ms |
11304 KB |
Output is correct |
8 |
Correct |
190 ms |
11348 KB |
Output is correct |
9 |
Incorrect |
200 ms |
11324 KB |
Output is incorrect: {s, t} is wrong. |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
36 ms |
9360 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
28 ms |
9336 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |