oj.uz

Submission #220128

# Submission time Handle Problem Language Result Execution time Memory
220128 2020-04-07T05:49:07 Z IgorI Highway Tolls (IOI18_highway) C++17
69 / 100
 317 ms 40648 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 < 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 (s1 == 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: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:155:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < qV.size(); i++)
                     ~~^~~~~~~~~~~
highway.cpp:170: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 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 640 KB Output is correct
2 Correct 20 ms 2928 KB Output is correct
3 Correct 179 ms 25852 KB Output is correct
4 Correct 188 ms 29108 KB Output is correct
5 Correct 186 ms 27956 KB Output is correct
6 Correct 182 ms 25380 KB Output is correct
7 Correct 200 ms 28012 KB Output is correct
8 Correct 186 ms 28360 KB Output is correct
9 Correct 188 ms 26180 KB Output is correct
10 Correct 192 ms 27640 KB Output is correct
11 Correct 214 ms 29380 KB Output is correct
12 Correct 206 ms 29524 KB Output is correct
13 Correct 210 ms 28820 KB Output is correct
14 Correct 206 ms 28204 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3236 KB Output is correct
2 Correct 35 ms 6316 KB Output is correct
3 Correct 64 ms 9276 KB Output is correct
4 Correct 157 ms 29916 KB Output is correct
5 Correct 157 ms 30100 KB Output is correct
6 Correct 173 ms 29076 KB Output is correct
7 Correct 180 ms 28032 KB Output is correct
8 Correct 166 ms 29764 KB Output is correct
9 Correct 171 ms 28808 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 512 KB Output is correct
2 Correct 23 ms 3372 KB Output is correct
3 Correct 139 ms 20192 KB Output is correct
4 Correct 176 ms 26276 KB Output is correct
5 Correct 178 ms 25824 KB Output is correct
6 Correct 175 ms 25484 KB Output is correct
7 Correct 172 ms 24680 KB Output is correct
8 Correct 191 ms 25132 KB Output is correct
9 Correct 191 ms 27864 KB Output is correct
10 Correct 193 ms 27916 KB Output is correct
11 Correct 230 ms 28316 KB Output is correct
12 Correct 210 ms 29140 KB Output is correct
13 Correct 209 ms 28732 KB Output is correct
14 Correct 197 ms 28840 KB Output is correct
15 Correct 168 ms 25140 KB Output is correct
16 Correct 174 ms 25128 KB Output is correct
17 Correct 222 ms 28576 KB Output is correct
18 Correct 202 ms 28260 KB Output is correct
19 Correct 175 ms 24824 KB Output is correct
20 Correct 206 ms 29516 KB Output is correct
21 Correct 154 ms 25648 KB Output is correct
22 Correct 157 ms 25072 KB Output is correct
23 Correct 176 ms 30140 KB Output is correct
24 Correct 191 ms 29744 KB Output is correct
25 Correct 206 ms 28436 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3376 KB Output is correct
2 Correct 26 ms 3656 KB Output is correct
3 Correct 221 ms 31584 KB Output is correct
4 Correct 251 ms 34116 KB Output is correct
5 Correct 277 ms 39660 KB Output is correct
6 Correct 279 ms 38944 KB Output is correct
7 Correct 272 ms 39448 KB Output is correct
8 Correct 275 ms 39316 KB Output is correct
9 Correct 182 ms 27968 KB Output is correct
10 Correct 162 ms 16768 KB Output is correct
11 Correct 204 ms 28248 KB Output is correct
12 Correct 259 ms 37344 KB Output is correct
13 Correct 261 ms 38240 KB Output is correct
14 Correct 317 ms 38860 KB Output is correct
15 Correct 270 ms 38644 KB Output is correct
16 Correct 224 ms 33692 KB Output is correct
17 Correct 168 ms 29036 KB Output is correct
18 Correct 180 ms 28560 KB Output is correct
19 Correct 187 ms 29660 KB Output is correct
20 Correct 188 ms 29876 KB Output is correct
21 Correct 261 ms 39080 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3528 KB Output is correct
2 Correct 24 ms 3404 KB Output is correct
3 Correct 224 ms 32908 KB Output is correct
4 Correct 218 ms 31560 KB Output is correct
5 Correct 230 ms 34636 KB Output is correct
6 Incorrect 277 ms 40648 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -