Submission #219740

#	Time	Username	Problem	Language	Result	Execution time	Memory
219740		IgorI	Highway Tolls (IOI18_highway)	C++17	0 / 100	17 ms	1408 KiB

highway

#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;

vector<pair<int, int> > bfs(int root, int d, 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<pair<int, int> > ans;
    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);
                if (curdist[y] == d)
                {
                    ans.push_back({y, id});
                }
            }
        }
    }
    return ans;
}

int solve_for_tree(int root, vector<int> edges)
{
    vector<int> q1(m, 1);
    for (int i = 0; i < edges.size(); i++) q1[edges[i]] = 0;
    long long d = ask(q1);

    int rootDist = (Dist * b - d) / (b - a);
    if (rootDist == 0)
    {
        return root;
    }
    vector<pair<int, int> > pos = bfs(root, rootDist, edges);
    int l = 0, r = pos.size();
    while (l + 1 < r)
    {
        int mid = (l + r) / 2;
        vector<int> w(m, 1);
        for (int i = l; i < mid; i++)
        {
            w[pos[i].second] = 0;
        }
        long long c = ask(w);
        if (c == Dist * b)
            l = mid;
        else
            r = mid;
    }
    return pos[l].first;
}

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;
    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];
    vector<int> dist(n, N);
    dist[V] = 0, dist[U] = 0;
    vector<int> from(n, N);
    from[V] = V, from[U] = U;
    vector<int> q = {V, U};
    vector<int> vecV, vecU;
    for (int i = 0; i < q.size(); i++)
    {
        int x = q[i];
        for (auto id : g[x])
        {
            int y = v[id] + u[id] - x;
            if (dist[y] == N)
            {
                dist[y] = dist[x] + 1;
                from[y] = from[x];
                if (from[y] == V) vecV.push_back(id);
                else vecU.push_back(id);
            }
        }
    }
    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";
    cout << "\n";
    answer(solve_for_tree(V, vecV), solve_for_tree(U, vecU));
}

#ifdef LOCAL
int 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 (stderr)

highway.cpp: In function 'std::vector<std::pair<int, int> > bfs(int, int, std::vector<int>)':
highway.cpp:44: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:48: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>)':
highway.cpp:71:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < edges.size(); i++) q1[edges[i]] = 0;
                     ~~^~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:137:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < q.size(); i++)
                     ~~^~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31