#ifdef LOCAL
#else
#include <highway.h>
#endif // LOCAL
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
#ifdef LOCAL
void answer(int s, int t)
{
cout << s << " " << t << endl;
exit(0);
}
long long ask(vector<int> w)
{
long long res;
for (int i = 0; i < w.size(); i++)
{
cout << w[i] << " ";
}
cout << endl;
cin >> res;
return res;
}
#endif // LOCAL
const int N = 200000;
int n, m, a, b;
vector<vector<int> > g;
vector<int> u, v;
long long Dist;
int linker;
struct tr{
int id, ver, dist;
};
bool comp(tr a, tr b)
{
return a.dist < b.dist;
}
vector<tr> bfs(int root, vector<int> use)
{
vector<int> curdist(n, N);
vector<int> ok(m);
for (int i = 0; i < use.size(); i++) ok[use[i]] = 1;
vector<int> q = {root};
curdist[root] = 0;
vector<tr> ans = {{linker, root, 0}};
for (int i = 0; i < q.size(); i++)
{
int x = q[i];
for (auto id : g[x])
{
int y = u[id] + v[id] - x;
if (ok[id] && curdist[y] == N)
{
curdist[y] = curdist[x] + 1;
q.push_back(y);
ans.push_back({id, y, curdist[y]});
}
}
}
return ans;
}
int solve_for_tree(int root, vector<int> edges, vector<int> others)
{
vector<tr> kek = bfs(root, edges);
sort(kek.begin(), kek.end(), comp);
int l = -1, r = kek.size() + 1;
while (l + 1 < r)
{
int mid = (l + r) / 2;
vector<int> w(m, 1);
for (auto it : others) w[it] = 0;
w[linker] = 0;
for (int i = 0; i < mid; i++) w[kek[i].id] = 0;
long long si = ask(w);
if (si != Dist * a)
l = mid;
else
r = mid;
}
#ifdef LOCAL
cerr << kek.size() << "\n";
for (int i = 0; i < kek.size(); i++)
{
cerr << kek[i].id << " " << kek[i].ver << " " << kek[i].dist << "\n";
}
#endif
return kek[l].ver;
}
void find_pair(int n0, vector<int> v0, vector<int> u0, int a0, int b0)
{
n = n0;
a = a0;
b = b0;
m = v0.size();
g.resize(n0);
v = v0, u = u0;
for (int i = 0; i < m; i++)
{
g[v[i]].push_back(i);
g[u[i]].push_back(i);
}
vector<int> q0(m);
Dist = ask(q0) / a;
int l = 0, r = m + 1;
while (l + 1 < r)
{
int mid = (l + r) / 2;
vector<int> q(m, 1);
for (int i = l; i < mid; i++)
{
q[i] = 0;
}
long long res = ask(q);
if (res == Dist * b)
l = mid;
else
r = mid;
}
int V = v[l];
int U = u[l];
linker = l;
vector<int> distV(n, N), distU(n, N), fromV(n), fromU(n);
distV[V] = 0, distU[U] = 0;
vector<int> qV = {V};
for (int i = 0; i < qV.size(); i++)
{
int x = qV[i];
for (auto id : g[x])
{
int y = v[id] + u[id] - x;
if (distV[y] == N)
{
distV[y] = distV[x] + 1;
qV.push_back(y);
fromV[y] = id;
}
}
}
vector<int> qU = {U};
for (int i = 0; i < qU.size(); i++)
{
int x = qU[i];
for (auto id : g[x])
{
int y = v[id] + u[id] - x;
if (distU[y] == N)
{
distU[y] = distU[x] + 1;
qU.push_back(y);
fromU[y] = id;
}
}
}
vector<int> vecV, vecU;
for (int i = 0; i < n; i++)
{
if (i != U) if (distU[i] <= distV[i]) vecU.push_back(fromU[i]);
if (i != V) if (distV[i] < distU[i]) vecV.push_back(fromV[i]);
}
#ifdef LOCAL
cerr << "determined : " << V << " " << U << "\n";
cerr << "tree (V) : ";
for (auto id : vecV) cerr << v[id] << " " << u[id] << "\n";
cerr << "\n";
cerr << "tree (U) : ";
for (auto id : vecU) cerr << v[id] << " " << u[id] << "\n";
cerr << "\n";
#endif // LOCAL
if (Dist == 1)
{
answer(V, U);
exit(0);
}
int s = solve_for_tree(V, vecV, vecU);
cerr << "determined s = " << s << "\n";
int t = solve_for_tree(U, vecU, vecV);
cerr << "determined t = " << t << "\n";
answer(s, t);
}
#ifdef LOCAL
signed main()
{
int n, m, a, b;
cin >> n >> m >> a >> b;
vector<int> v(m), u(m);
for (int i = 0; i < m; i++)
{
cin >> v[i] >> u[i];
}
find_pair(n, v, u, a, b);
}
#endif // LOCAL
Compilation message
highway.cpp: In function 'std::vector<tr> bfs(int, std::vector<int>)':
highway.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < use.size(); i++) ok[use[i]] = 1;
~~^~~~~~~~~~~~
highway.cpp:58:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < q.size(); i++)
~~^~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:140:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < qV.size(); i++)
~~^~~~~~~~~~~
highway.cpp:155:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < qU.size(); i++)
~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
512 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
1984 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
512 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
2040 KB |
Output is correct |
| 2 |
Correct |
22 ms |
2048 KB |
Output is correct |
| 3 |
Correct |
193 ms |
14656 KB |
Output is correct |
| 4 |
Correct |
228 ms |
13816 KB |
Output is correct |
| 5 |
Correct |
260 ms |
14596 KB |
Output is correct |
| 6 |
Correct |
250 ms |
15888 KB |
Output is correct |
| 7 |
Correct |
249 ms |
15580 KB |
Output is correct |
| 8 |
Correct |
254 ms |
14580 KB |
Output is correct |
| 9 |
Incorrect |
165 ms |
9028 KB |
Output is incorrect: {s, t} is wrong. |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
1912 KB |
Output is correct |
| 2 |
Correct |
23 ms |
2040 KB |
Output is correct |
| 3 |
Correct |
202 ms |
13668 KB |
Output is correct |
| 4 |
Correct |
200 ms |
14784 KB |
Output is correct |
| 5 |
Correct |
219 ms |
14824 KB |
Output is correct |
| 6 |
Incorrect |
258 ms |
14524 KB |
Output is incorrect: {s, t} is wrong. |
| 7 |
Halted |
0 ms |
0 KB |
- |
