oj.uz

Submission #220130

# Submission time Handle Problem Language Result Execution time Memory
220130 2020-04-07T05:53:19 Z IgorI Highway Tolls (IOI18_highway) C++17
69 / 100
 281 ms 39684 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;
    }
    l = r;
    #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 < l; i++) w1[kek[i].id] = 0;
    for (int i = 0; i <= l; i++) w2[kek[i].id] = 0;
    long long s1 = myask(w1), s2 = myask(w2);
    if (s2 != Dist * a) exit(1);
    //if (s1 != Dist * a && s2 == Dist * a)
        return kek[l].ver;
    //exit(1);
}

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:15: warning: unused variable 's1' [-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:156:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < qV.size(); i++)
                     ~~^~~~~~~~~~~
highway.cpp:171: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 380 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 5 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 20 ms 2920 KB Output is correct
3 Correct 197 ms 25908 KB Output is correct
4 Correct 197 ms 28676 KB Output is correct
5 Correct 194 ms 28300 KB Output is correct
6 Correct 180 ms 25820 KB Output is correct
7 Correct 190 ms 28472 KB Output is correct
8 Correct 180 ms 28664 KB Output is correct
9 Correct 176 ms 25524 KB Output is correct
10 Correct 186 ms 27256 KB Output is correct
11 Correct 205 ms 29800 KB Output is correct
12 Correct 217 ms 29660 KB Output is correct
13 Correct 197 ms 28600 KB Output is correct
14 Correct 209 ms 27892 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3268 KB Output is correct
2 Correct 33 ms 6304 KB Output is correct
3 Correct 59 ms 9144 KB Output is correct
4 Correct 160 ms 29788 KB Output is correct
5 Correct 157 ms 30384 KB Output is correct
6 Correct 159 ms 29956 KB Output is correct
7 Correct 175 ms 28180 KB Output is correct
8 Correct 168 ms 30136 KB Output is correct
9 Correct 173 ms 29500 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 25 ms 3192 KB Output is correct
3 Correct 136 ms 20952 KB Output is correct
4 Correct 185 ms 26140 KB Output is correct
5 Correct 181 ms 25468 KB Output is correct
6 Correct 171 ms 25400 KB Output is correct
7 Correct 176 ms 25060 KB Output is correct
8 Correct 178 ms 24824 KB Output is correct
9 Correct 198 ms 28576 KB Output is correct
10 Correct 192 ms 27924 KB Output is correct
11 Correct 210 ms 27740 KB Output is correct
12 Correct 217 ms 28892 KB Output is correct
13 Correct 206 ms 28724 KB Output is correct
14 Correct 208 ms 29176 KB Output is correct
15 Correct 167 ms 24768 KB Output is correct
16 Correct 178 ms 25880 KB Output is correct
17 Correct 217 ms 28216 KB Output is correct
18 Correct 201 ms 27864 KB Output is correct
19 Correct 182 ms 25156 KB Output is correct
20 Correct 232 ms 29504 KB Output is correct
21 Correct 145 ms 25328 KB Output is correct
22 Correct 162 ms 25428 KB Output is correct
23 Correct 175 ms 30400 KB Output is correct
24 Correct 193 ms 30032 KB Output is correct
25 Correct 212 ms 28060 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3504 KB Output is correct
2 Correct 27 ms 3488 KB Output is correct
3 Correct 233 ms 31240 KB Output is correct
4 Correct 245 ms 33760 KB Output is correct
5 Correct 278 ms 39684 KB Output is correct
6 Correct 277 ms 39024 KB Output is correct
7 Correct 268 ms 38976 KB Output is correct
8 Correct 277 ms 39416 KB Output is correct
9 Correct 183 ms 27484 KB Output is correct
10 Correct 169 ms 16764 KB Output is correct
11 Correct 225 ms 28740 KB Output is correct
12 Correct 257 ms 38472 KB Output is correct
13 Correct 271 ms 37768 KB Output is correct
14 Correct 281 ms 39432 KB Output is correct
15 Correct 270 ms 39200 KB Output is correct
16 Correct 217 ms 34020 KB Output is correct
17 Correct 167 ms 29272 KB Output is correct
18 Correct 187 ms 29188 KB Output is correct
19 Correct 183 ms 29644 KB Output is correct
20 Correct 182 ms 29528 KB Output is correct
21 Correct 270 ms 38684 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3448 KB Output is correct
2 Correct 24 ms 3536 KB Output is correct
3 Correct 219 ms 32520 KB Output is correct
4 Correct 218 ms 31552 KB Output is correct
5 Correct 234 ms 34536 KB Output is correct
6 Runtime error 238 ms 31456 KB Execution failed because the return code was nonzero
7 Halted 0 ms 0 KB -