#include <bits/stdc++.h>
#include "highway.h"
#define pii pair<int, int>
#define F first
#define S second
#define int long long
using namespace std;
const int MX = 9e4 + 100;
vector<pii> G1[MX], G2[MX];
bitset<MX> pass, edge;
int deep[MX];
//void answer(int a, int b) {
// cout << "! " << a << ' ' << b;
//}
//int ask(vector<int32_t> v) {
// for(auto it: v) cout << it << ' '; cout << endl;
// int val; cin >> val; return val;
//}
vector<pii> que;
void dfs(int u, int l, int d) {
que.push_back({u, l});
deep[u] = d;
for(auto it: G2[u]) {
dfs(it.F, it.S, d + 1);
}
}
void find_pair(int32_t n, vector<int32_t> u, vector<int32_t> v, int32_t a, int32_t b) {
for(int i = 0; i < u.size(); i ++) {
G1[u[i]].push_back({v[i], i});
G1[v[i]].push_back({u[i], i});
}
int d = ask(vector<int32_t>(u.size(), 0)) / a;
int l = 0, r = u.size() - 1;
while(l != r) {
int m = l + r >> 1;
vector<int32_t> query(u.size(), 0);
for(int j = l; j <= m; j ++) query[j] = 1;
if(ask(query) > d * a) r = m;
else l = m + 1;
}
pass[u[l]] = pass[v[l]] = edge[l] = true;
queue<pii> q;
q.push({u[l], l});
q.push({v[l], l});
while(q.size()) {
pii p = q.front(); q.pop();
for(auto i: G1[p.F]) {
if(!pass[i.F]) {
edge[i.S] = true;
pass[i.F] = true;
G2[p.F].push_back(i);
q.push(p);
}
}
}
int x, y;
{
que.clear();
dfs(u[l], l, 1);
sort(que.begin(), que.end(), [](pii a, pii b) {
return deep[a.F] < deep[b.F];
});
int l = 0, r = que.size() - 1;
while(l != r) {
int m = l + r >> 1;
vector<int32_t> query(u.size(), 1);
for(int i = 0; i < u.size(); i ++) {
if(edge[i]) query[i] = 0;
}
for(int i = m + 1; i <= r; i ++) {
query[que[i].S] = 1;
}
if(ask(query) > d * a) l = m + 1;
else r = m;
}
x = que[l].F;
}
{
que.clear();
dfs(v[l], l, 1);
sort(que.begin(), que.end(), [](pii a, pii b) {
return deep[a.F] < deep[b.F];
});
int l = 0, r = que.size() - 1;
while(l != r) {
int m = l + r >> 1;
vector<int32_t> query(u.size(), 1);
for(int i = 0; i < u.size(); i ++) {
if(edge[i]) query[i] = 0;
}
for(int i = m + 1; i <= r; i ++) {
query[que[i].S] = 1;
}
if(ask(query) > d * a) l = m + 1;
else r = m;
}
y = que[l].F;
}
answer(x, y);
}
//main () {
// find_pair(3, {0, 1, 2}, {1, 2, 0}, 1, 2);
//}
Compilation message
highway.cpp: In function 'void find_pair(int32_t, std::vector<int>, std::vector<int>, int32_t, int32_t)':
highway.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < u.size(); i ++) {
~~^~~~~~~~~~
highway.cpp:35:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
highway.cpp:65:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
highway.cpp:67:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < u.size(); i ++) {
~~^~~~~~~~~~
highway.cpp:86:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
highway.cpp:88:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < u.size(); i ++) {
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4520 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4600 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
5240 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4600 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
5396 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
5400 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
