oj.uz

Submission #220132

# Submission time Handle Problem Language Result Execution time Memory
220132 2020-04-07T05:55:11 Z IgorI Highway Tolls (IOI18_highway) C++17
69 / 100
 304 ms 39568 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 (s2 != Dist * a) 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: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 6 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 6 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 392 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 KB Output is correct
2 Correct 21 ms 2988 KB Output is correct
3 Correct 208 ms 25844 KB Output is correct
4 Correct 229 ms 28628 KB Output is correct
5 Correct 205 ms 28280 KB Output is correct
6 Correct 204 ms 25840 KB Output is correct
7 Correct 206 ms 28536 KB Output is correct
8 Correct 203 ms 28664 KB Output is correct
9 Correct 203 ms 25488 KB Output is correct
10 Correct 219 ms 27208 KB Output is correct
11 Correct 231 ms 29700 KB Output is correct
12 Correct 234 ms 29496 KB Output is correct
13 Correct 211 ms 28556 KB Output is correct
14 Correct 233 ms 27848 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3272 KB Output is correct
2 Correct 34 ms 6384 KB Output is correct
3 Correct 67 ms 9144 KB Output is correct
4 Correct 181 ms 29764 KB Output is correct
5 Correct 164 ms 30480 KB Output is correct
6 Correct 170 ms 29876 KB Output is correct
7 Correct 183 ms 28192 KB Output is correct
8 Correct 172 ms 30100 KB Output is correct
9 Correct 170 ms 29392 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 22 ms 3320 KB Output is correct
3 Correct 169 ms 20732 KB Output is correct
4 Correct 188 ms 26232 KB Output is correct
5 Correct 205 ms 25464 KB Output is correct
6 Correct 193 ms 25460 KB Output is correct
7 Correct 184 ms 25144 KB Output is correct
8 Correct 209 ms 24700 KB Output is correct
9 Correct 214 ms 28700 KB Output is correct
10 Correct 219 ms 27944 KB Output is correct
11 Correct 220 ms 27820 KB Output is correct
12 Correct 200 ms 28760 KB Output is correct
13 Correct 217 ms 28744 KB Output is correct
14 Correct 235 ms 29164 KB Output is correct
15 Correct 195 ms 24712 KB Output is correct
16 Correct 203 ms 25848 KB Output is correct
17 Correct 217 ms 28172 KB Output is correct
18 Correct 220 ms 27868 KB Output is correct
19 Correct 196 ms 25108 KB Output is correct
20 Correct 239 ms 29444 KB Output is correct
21 Correct 153 ms 25348 KB Output is correct
22 Correct 187 ms 25380 KB Output is correct
23 Correct 193 ms 30576 KB Output is correct
24 Correct 196 ms 29988 KB Output is correct
25 Correct 253 ms 27964 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3504 KB Output is correct
2 Correct 29 ms 3504 KB Output is correct
3 Correct 229 ms 31312 KB Output is correct
4 Correct 249 ms 33676 KB Output is correct
5 Correct 301 ms 39508 KB Output is correct
6 Correct 262 ms 38876 KB Output is correct
7 Correct 272 ms 38924 KB Output is correct
8 Correct 280 ms 39464 KB Output is correct
9 Correct 192 ms 27472 KB Output is correct
10 Correct 174 ms 16908 KB Output is correct
11 Correct 202 ms 28720 KB Output is correct
12 Correct 263 ms 38340 KB Output is correct
13 Correct 263 ms 37764 KB Output is correct
14 Correct 287 ms 39568 KB Output is correct
15 Correct 304 ms 39192 KB Output is correct
16 Correct 225 ms 34116 KB Output is correct
17 Correct 178 ms 29396 KB Output is correct
18 Correct 183 ms 29220 KB Output is correct
19 Correct 188 ms 29644 KB Output is correct
20 Correct 186 ms 29604 KB Output is correct
21 Correct 275 ms 38628 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 25 ms 3516 KB Output is correct
3 Correct 213 ms 32452 KB Output is correct
4 Correct 233 ms 31616 KB Output is correct
5 Correct 236 ms 34516 KB Output is correct
6 Incorrect 279 ms 39548 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -