제출 #219731

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
219731		IgorI	통행료 (IOI18_highway)	C++17	12 / 100	148 ms	10864 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 (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> bad)
{
    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> edges, others;
    vector<int> q0(m);
    Dist = ask(q0) / a;
    for (int i = 0; i < m; i++) edges.push_back(i);
    answer(solve_for_tree(0, edges, others), 0);
}

#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

컴파일 시 표준 에러 (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>, 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;
                     ~~^~~~~~~~~~~~~~

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