oj.uz

Submission #220135

# Submission time Handle Problem Language Result Execution time Memory
220135 2020-04-07T05:58:35 Z IgorI Highway Tolls (IOI18_highway) C++17
69 / 100
 292 ms 39552 KB 
#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);
    if (r == kek.size() + 1) exit(1);
    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);
    }
    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";

    //vector<int> all;
    //for (int i = 0; i < m; i++) all.push_back(i);
    //vector<tr> kek = bfs(s, all);
    //int tt = 0;
    //for (int i = 0; i < kek.size(); i++) if (kek[i].ver == t) tt = (kek[i].dist == Dist);
    //if (tt == 0)
    //    exit(1);

    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:112:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (r == kek.size() + 1) exit(1);
         ~~^~~~~~~~~~~~~~~~~
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:153:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < qV.size(); i++)
                     ~~^~~~~~~~~~~
highway.cpp:168:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < qU.size(); i++)
                     ~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 22 ms 2920 KB Output is correct
3 Correct 205 ms 25920 KB Output is correct
4 Correct 203 ms 28604 KB Output is correct
5 Correct 200 ms 28320 KB Output is correct
6 Correct 190 ms 25868 KB Output is correct
7 Correct 264 ms 28332 KB Output is correct
8 Correct 185 ms 28636 KB Output is correct
9 Correct 201 ms 25552 KB Output is correct
10 Correct 222 ms 27264 KB Output is correct
11 Correct 292 ms 29760 KB Output is correct
12 Correct 208 ms 29460 KB Output is correct
13 Correct 254 ms 28580 KB Output is correct
14 Correct 205 ms 27776 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3268 KB Output is correct
2 Correct 36 ms 6296 KB Output is correct
3 Correct 61 ms 9120 KB Output is correct
4 Correct 160 ms 29676 KB Output is correct
5 Correct 157 ms 30368 KB Output is correct
6 Correct 162 ms 29824 KB Output is correct
7 Correct 167 ms 28224 KB Output is correct
8 Correct 160 ms 30156 KB Output is correct
9 Correct 166 ms 29408 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 19 ms 3260 KB Output is correct
3 Correct 130 ms 20676 KB Output is correct
4 Correct 180 ms 26212 KB Output is correct
5 Correct 188 ms 25464 KB Output is correct
6 Correct 172 ms 25404 KB Output is correct
7 Correct 181 ms 25052 KB Output is correct
8 Correct 172 ms 24700 KB Output is correct
9 Correct 194 ms 28632 KB Output is correct
10 Correct 201 ms 27976 KB Output is correct
11 Correct 196 ms 27764 KB Output is correct
12 Correct 202 ms 28824 KB Output is correct
13 Correct 202 ms 28760 KB Output is correct
14 Correct 212 ms 29168 KB Output is correct
15 Correct 169 ms 24780 KB Output is correct
16 Correct 177 ms 25776 KB Output is correct
17 Correct 201 ms 28104 KB Output is correct
18 Correct 194 ms 27824 KB Output is correct
19 Correct 183 ms 25220 KB Output is correct
20 Correct 207 ms 29408 KB Output is correct
21 Correct 160 ms 25408 KB Output is correct
22 Correct 156 ms 25304 KB Output is correct
23 Correct 189 ms 30440 KB Output is correct
24 Correct 189 ms 29908 KB Output is correct
25 Correct 215 ms 28124 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3380 KB Output is correct
2 Correct 23 ms 3528 KB Output is correct
3 Correct 237 ms 31392 KB Output is correct
4 Correct 238 ms 33684 KB Output is correct
5 Correct 280 ms 39552 KB Output is correct
6 Correct 268 ms 38840 KB Output is correct
7 Correct 271 ms 39020 KB Output is correct
8 Correct 274 ms 39420 KB Output is correct
9 Correct 182 ms 27360 KB Output is correct
10 Correct 165 ms 16680 KB Output is correct
11 Correct 203 ms 28732 KB Output is correct
12 Correct 250 ms 38468 KB Output is correct
13 Correct 268 ms 37712 KB Output is correct
14 Correct 283 ms 39352 KB Output is correct
15 Correct 260 ms 39200 KB Output is correct
16 Correct 221 ms 33964 KB Output is correct
17 Correct 167 ms 29504 KB Output is correct
18 Correct 177 ms 29204 KB Output is correct
19 Correct 181 ms 29736 KB Output is correct
20 Correct 180 ms 29404 KB Output is correct
21 Correct 252 ms 38592 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3448 KB Output is correct
2 Correct 24 ms 3532 KB Output is correct
3 Correct 218 ms 32532 KB Output is correct
4 Correct 212 ms 31652 KB Output is correct
5 Correct 229 ms 34524 KB Output is correct
6 Runtime error 240 ms 31472 KB Execution failed because the return code was nonzero
7 Halted 0 ms 0 KB -