#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;
}
map<vector<int>, long long> mm;
long long myask(vector<int> w)
{
if (mm.find(w) != mm.end()) return mm[w];
return mm[w] = ask(w);
}
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;
for (int i = 0; i <= mid; i++) w[kek[i].id] = 0;
long long si = myask(w);
if (si == Dist * a)
r = mid;
else
l = 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
vector<int> w1(m, 1), w2(m, 1);
for (auto it : others) w1[it] = 0, w2[it] = 0;
for (int i = 0; i < r; i++) w1[kek[i].id] = 0;
for (int i = 0; i <= r; i++) w2[kek[i].id] = 0;
long long s1 = myask(w1), s2 = myask(w2);
return kek[r].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 = myask(q0) / a;
int l = -1, 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 = myask(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);
}
vector<int> w(m, 1);
for (auto it : vecU) w[it] = 0;
for (auto it : vecV) w[it] = 0;
long long si = myask(w);
if (si != Dist * a) exit(1);
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:62: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:66:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < q.size(); i++)
~~^~~~~~~~~~
highway.cpp: In function 'int solve_for_tree(int, std::vector<int>, std::vector<int>)':
highway.cpp:111:15: warning: unused variable 's1' [-Wunused-variable]
long long s1 = myask(w1), s2 = myask(w2);
^~
highway.cpp:111:31: warning: unused variable 's2' [-Wunused-variable]
long long s1 = myask(w1), s2 = myask(w2);
^~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:152:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < qV.size(); i++)
~~^~~~~~~~~~~
highway.cpp:167: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 |
Runtime error |
5 ms |
384 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
512 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
2176 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
512 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
2296 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
2304 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
