#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
array<int, 5> seeds = {409887653, 59456231, 56246231, 56246233, 931621953};
mt19937 rng(seeds[(std::chrono::duration_cast<std::chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()^179921)%seeds.size()]);
int get_rand(int l, int r){
return uniform_int_distribution<int>(l, r)(rng);
}
int A, B, C, M, n;
ll initial;
int path_len;
int ed;
vector<vector<pair<int, int> > > g;
map<pair<int, int>, int> deco;
vector<char> state;
vector<int> gord;
bool rec(int u, int p, int pared){
assert(state[u] == 0);
state[u] = 1;
int pool = -1;
auto add_cand = [&](int e){
if(pool == -1){
pool = e;
} else {
gord.push_back(pool);
gord.push_back(e);
pool = -1;
}
};
for(auto const&e:g[u]){
if(e.first == p) continue;
if(state[e.first] == 0){
bool did = rec(e.first, u, e.second);
if(!did){
add_cand(e.second);
}
} else if(state[e.first] == 1){
add_cand(e.second);
}
}
state[u] = 2;
if(pool != -1){
gord.push_back(pool);
gord.push_back(pared);
return true;
}
return false;
}
vector<int> line_graph_allign(){
state.assign(n, 0);
gord.clear();
rec(get_rand(0, n-1), -1, -1);
if(M%2){
assert(gord.back() == -1);
gord.pop_back();
gord.push_back(gord.back());
}
return gord;
}
int find_vertex(int M, vector<int> const&U, vector<int> const&V){
vector<int> ord = line_graph_allign();
for(int i=0;i<ord.size();i+=2){
int j = 2*get_rand(0, i/2);
swap(ord[i], ord[i-j]);
swap(ord[i+1], ord[i-j+1]);
}
/*for(int i=0;i<ord.size();i+=2){
cerr << U[ord[i]] << " " << V[i] << " | " << U[i+1] << " " << V[i+1] << "\n";
}*/
int l = -1, r = (M+1)/2-1;
while(l+1 < r){
int m = l + (r-l)/2;
vector<int> v(M, 1);
for(int i=0;i/2<=m;++i) v[ord[i]] = 0;
ll mid = ask(v);
if(mid == path_len*(ll)A){
r = m;
} else {
l = m;
}
}
map<int, int> cnt;
for(auto const&e:{U, V}){
for(auto const&i:{ord[2*r], ord[2*r+1]}){
++cnt[e[i]];
}
}
for(auto const&e:cnt){
if(e.second == 2){
return e.first;
}
}
assert(0);
return -1;
}
int far_search(int u, vector<int> const&U, vector<int> const&V, bool fix_d){
vector<int> ord, vis(n, 0);
vector<int> inv_ord(n);
vector<int> d;
ord.push_back(u);
d.push_back(0);
vis[u] = 1;
for(int i=0;i<(int)ord.size();++i){
int v = ord[i];
inv_ord[v] = i;
for(auto const&f:g[v]){
auto const e = f.first;
if(!vis[e]){
vis[e] = 1;
ord.push_back(e);
d.push_back(d[i]+1);
}
}
}
assert((int)ord.size() == n);
int l = 0, r = n;
if(fix_d){
l = lower_bound(d.begin(), d.end(), path_len) - d.begin();
r = upper_bound(d.begin(), d.end(), path_len) - d.begin();
}
while(l+1 < r){
int m = l + (r-l)/2;
vector<int> v(M, 1);
for(int i=0;i<M;++i){
if(inv_ord[U[i]] < m && inv_ord[V[i]] < m){
v[i] = 0;
}
}
ll dist = ask(v);
if(dist == path_len * (ll) A){
r = m;
} else {
l = m;
}
}
return ord[l];
}
void find_pair(int N, vector<int> U, vector<int> V, int A_, int B_) {
n=N; A=A_; B=B_;
C = B-A;
M = U.size();
for(int i=0;i<M;++i){
deco[make_pair(U[i], V[i])] = i;
deco[make_pair(V[i], U[i])] = i;
}
initial = ask(vector<int>(M, 1));
assert(initial % B == 0);
path_len = initial / B;
//if(path_len <= 2) ask(vector<int>(M, 1));
g.assign(N, vector<pair<int, int> >());
for(int i=0;i<M;++i){
g[U[i]].emplace_back(V[i], i);
g[V[i]].emplace_back(U[i], i);
}
for(auto &e:g) shuffle(e.begin(), e.end(), rng);
int start = find_vertex(M, U, V);
//cerr << "ed " << ed << " : " << U[ed] << " " << V[ed] << "\n";
const int S = far_search(start, U, V, false);
const int T = far_search(S, U, V, true);
answer(S, T);
}
Compilation message
highway.cpp: In function 'int find_vertex(int, const std::vector<int>&, const std::vector<int>&)':
highway.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ord.size();i+=2){
~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
336 KB |
Output is correct |
3 |
Correct |
2 ms |
248 KB |
Output is correct |
4 |
Correct |
2 ms |
248 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
248 KB |
Output is correct |
8 |
Correct |
2 ms |
312 KB |
Output is correct |
9 |
Correct |
2 ms |
420 KB |
Output is correct |
10 |
Correct |
2 ms |
296 KB |
Output is correct |
11 |
Correct |
2 ms |
336 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
504 KB |
Output is correct |
2 |
Correct |
35 ms |
2668 KB |
Output is correct |
3 |
Correct |
395 ms |
21224 KB |
Output is correct |
4 |
Correct |
358 ms |
21320 KB |
Output is correct |
5 |
Correct |
403 ms |
21232 KB |
Output is correct |
6 |
Correct |
434 ms |
21224 KB |
Output is correct |
7 |
Correct |
417 ms |
21236 KB |
Output is correct |
8 |
Correct |
399 ms |
21244 KB |
Output is correct |
9 |
Correct |
366 ms |
21236 KB |
Output is correct |
10 |
Correct |
409 ms |
21224 KB |
Output is correct |
11 |
Correct |
413 ms |
22832 KB |
Output is correct |
12 |
Correct |
387 ms |
23292 KB |
Output is correct |
13 |
Correct |
400 ms |
22516 KB |
Output is correct |
14 |
Correct |
378 ms |
22416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
3404 KB |
Output is correct |
2 |
Correct |
57 ms |
6584 KB |
Output is correct |
3 |
Correct |
80 ms |
8540 KB |
Output is correct |
4 |
Correct |
220 ms |
28632 KB |
Output is correct |
5 |
Correct |
258 ms |
28468 KB |
Output is correct |
6 |
Correct |
255 ms |
26300 KB |
Output is correct |
7 |
Correct |
245 ms |
26804 KB |
Output is correct |
8 |
Correct |
268 ms |
28372 KB |
Output is correct |
9 |
Correct |
265 ms |
26888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
508 KB |
Output is correct |
2 |
Correct |
26 ms |
2632 KB |
Output is correct |
3 |
Correct |
306 ms |
16580 KB |
Output is correct |
4 |
Correct |
382 ms |
21312 KB |
Output is correct |
5 |
Correct |
366 ms |
21224 KB |
Output is correct |
6 |
Correct |
381 ms |
21220 KB |
Output is correct |
7 |
Correct |
350 ms |
21228 KB |
Output is correct |
8 |
Correct |
392 ms |
21208 KB |
Output is correct |
9 |
Correct |
427 ms |
21224 KB |
Output is correct |
10 |
Correct |
395 ms |
21244 KB |
Output is correct |
11 |
Correct |
418 ms |
22524 KB |
Output is correct |
12 |
Correct |
495 ms |
22584 KB |
Output is correct |
13 |
Correct |
420 ms |
22948 KB |
Output is correct |
14 |
Correct |
397 ms |
23364 KB |
Output is correct |
15 |
Correct |
370 ms |
21240 KB |
Output is correct |
16 |
Correct |
367 ms |
20872 KB |
Output is correct |
17 |
Correct |
393 ms |
22448 KB |
Output is correct |
18 |
Correct |
369 ms |
23428 KB |
Output is correct |
19 |
Correct |
381 ms |
21248 KB |
Output is correct |
20 |
Correct |
404 ms |
24132 KB |
Output is correct |
21 |
Correct |
398 ms |
21404 KB |
Output is correct |
22 |
Correct |
373 ms |
21424 KB |
Output is correct |
23 |
Correct |
353 ms |
21460 KB |
Output is correct |
24 |
Correct |
363 ms |
22168 KB |
Output is correct |
25 |
Correct |
417 ms |
26260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
2996 KB |
Output is correct |
2 |
Correct |
43 ms |
3188 KB |
Output is correct |
3 |
Correct |
452 ms |
24564 KB |
Output is correct |
4 |
Correct |
513 ms |
27204 KB |
Output is correct |
5 |
Correct |
622 ms |
31740 KB |
Output is correct |
6 |
Correct |
594 ms |
31756 KB |
Output is correct |
7 |
Correct |
622 ms |
31584 KB |
Output is correct |
8 |
Correct |
574 ms |
31720 KB |
Output is correct |
9 |
Correct |
506 ms |
24336 KB |
Output is correct |
10 |
Correct |
538 ms |
24828 KB |
Output is correct |
11 |
Correct |
565 ms |
25408 KB |
Output is correct |
12 |
Correct |
580 ms |
30820 KB |
Output is correct |
13 |
Correct |
611 ms |
31312 KB |
Output is correct |
14 |
Correct |
624 ms |
33136 KB |
Output is correct |
15 |
Correct |
593 ms |
33156 KB |
Output is correct |
16 |
Correct |
584 ms |
28352 KB |
Output is correct |
17 |
Correct |
444 ms |
21564 KB |
Output is correct |
18 |
Correct |
402 ms |
21736 KB |
Output is correct |
19 |
Correct |
409 ms |
21720 KB |
Output is correct |
20 |
Correct |
406 ms |
21808 KB |
Output is correct |
21 |
Correct |
606 ms |
30368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
2976 KB |
Output is correct |
2 |
Correct |
41 ms |
3260 KB |
Output is correct |
3 |
Correct |
452 ms |
24856 KB |
Output is correct |
4 |
Correct |
487 ms |
25908 KB |
Output is correct |
5 |
Correct |
504 ms |
27156 KB |
Output is correct |
6 |
Correct |
568 ms |
31688 KB |
Output is correct |
7 |
Correct |
431 ms |
24872 KB |
Output is correct |
8 |
Correct |
459 ms |
25908 KB |
Output is correct |
9 |
Correct |
510 ms |
27328 KB |
Output is correct |
10 |
Correct |
594 ms |
31788 KB |
Output is correct |
11 |
Correct |
610 ms |
31692 KB |
Output is correct |
12 |
Correct |
568 ms |
31720 KB |
Output is correct |
13 |
Correct |
563 ms |
25320 KB |
Output is correct |
14 |
Correct |
692 ms |
24824 KB |
Output is correct |
15 |
Correct |
572 ms |
25300 KB |
Output is correct |
16 |
Correct |
571 ms |
24788 KB |
Output is correct |
17 |
Correct |
604 ms |
25408 KB |
Output is correct |
18 |
Correct |
580 ms |
24724 KB |
Output is correct |
19 |
Correct |
552 ms |
31448 KB |
Output is correct |
20 |
Correct |
619 ms |
32320 KB |
Output is correct |
21 |
Correct |
608 ms |
33256 KB |
Output is correct |
22 |
Correct |
596 ms |
33248 KB |
Output is correct |
23 |
Correct |
542 ms |
33092 KB |
Output is correct |
24 |
Correct |
638 ms |
33304 KB |
Output is correct |
25 |
Correct |
604 ms |
33292 KB |
Output is correct |
26 |
Correct |
621 ms |
33200 KB |
Output is correct |
27 |
Correct |
398 ms |
21740 KB |
Output is correct |
28 |
Correct |
382 ms |
21688 KB |
Output is correct |
29 |
Correct |
418 ms |
21932 KB |
Output is correct |
30 |
Partially correct |
394 ms |
21924 KB |
Output is partially correct |
31 |
Partially correct |
377 ms |
21664 KB |
Output is partially correct |
32 |
Correct |
429 ms |
21600 KB |
Output is correct |
33 |
Correct |
388 ms |
21972 KB |
Output is correct |
34 |
Correct |
369 ms |
21844 KB |
Output is correct |
35 |
Correct |
413 ms |
21612 KB |
Output is correct |
36 |
Correct |
404 ms |
21596 KB |
Output is correct |
37 |
Correct |
418 ms |
22008 KB |
Output is correct |
38 |
Correct |
448 ms |
22304 KB |
Output is correct |
39 |
Correct |
583 ms |
31476 KB |
Output is correct |
40 |
Correct |
561 ms |
31268 KB |
Output is correct |
41 |
Correct |
593 ms |
30528 KB |
Output is correct |
42 |
Correct |
509 ms |
29976 KB |
Output is correct |