oj.uz

Submission #220127

# Submission time Handle Problem Language Result Execution time Memory
220127 2020-04-07T05:45:45 Z IgorI Highway Tolls (IOI18_highway) C++17
69 / 100
 282 ms 40596 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 && 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 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:158:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < qV.size(); i++)
                     ~~^~~~~~~~~~~
highway.cpp:173: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 288 KB Output is correct
6 Correct 6 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 19 ms 2928 KB Output is correct
3 Correct 187 ms 25808 KB Output is correct
4 Correct 193 ms 29156 KB Output is correct
5 Correct 190 ms 27952 KB Output is correct
6 Correct 193 ms 25396 KB Output is correct
7 Correct 205 ms 27936 KB Output is correct
8 Correct 181 ms 28264 KB Output is correct
9 Correct 190 ms 26168 KB Output is correct
10 Correct 201 ms 27516 KB Output is correct
11 Correct 219 ms 29320 KB Output is correct
12 Correct 208 ms 29552 KB Output is correct
13 Correct 196 ms 28556 KB Output is correct
14 Correct 196 ms 28236 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3232 KB Output is correct
2 Correct 36 ms 6288 KB Output is correct
3 Correct 59 ms 9272 KB Output is correct
4 Correct 163 ms 29856 KB Output is correct
5 Correct 168 ms 30100 KB Output is correct
6 Correct 161 ms 29076 KB Output is correct
7 Correct 182 ms 27872 KB Output is correct
8 Correct 164 ms 29800 KB Output is correct
9 Correct 177 ms 28696 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 3360 KB Output is correct
3 Correct 129 ms 20180 KB Output is correct
4 Correct 175 ms 26164 KB Output is correct
5 Correct 170 ms 25868 KB Output is correct
6 Correct 183 ms 25384 KB Output is correct
7 Correct 182 ms 24888 KB Output is correct
8 Correct 175 ms 25036 KB Output is correct
9 Correct 198 ms 28028 KB Output is correct
10 Correct 193 ms 27956 KB Output is correct
11 Correct 204 ms 28136 KB Output is correct
12 Correct 213 ms 29196 KB Output is correct
13 Correct 205 ms 28688 KB Output is correct
14 Correct 222 ms 28936 KB Output is correct
15 Correct 173 ms 25144 KB Output is correct
16 Correct 185 ms 25272 KB Output is correct
17 Correct 202 ms 28480 KB Output is correct
18 Correct 204 ms 28212 KB Output is correct
19 Correct 171 ms 24768 KB Output is correct
20 Correct 201 ms 29400 KB Output is correct
21 Correct 151 ms 25764 KB Output is correct
22 Correct 153 ms 25076 KB Output is correct
23 Correct 178 ms 30052 KB Output is correct
24 Correct 197 ms 29732 KB Output is correct
25 Correct 215 ms 28564 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3376 KB Output is correct
2 Correct 24 ms 3528 KB Output is correct
3 Correct 228 ms 31700 KB Output is correct
4 Correct 230 ms 34156 KB Output is correct
5 Correct 276 ms 39580 KB Output is correct
6 Correct 264 ms 38952 KB Output is correct
7 Correct 282 ms 39360 KB Output is correct
8 Correct 276 ms 39344 KB Output is correct
9 Correct 190 ms 27964 KB Output is correct
10 Correct 164 ms 16760 KB Output is correct
11 Correct 206 ms 28152 KB Output is correct
12 Correct 252 ms 37420 KB Output is correct
13 Correct 264 ms 38184 KB Output is correct
14 Correct 276 ms 38888 KB Output is correct
15 Correct 272 ms 38580 KB Output is correct
16 Correct 275 ms 33516 KB Output is correct
17 Correct 169 ms 29028 KB Output is correct
18 Correct 184 ms 28464 KB Output is correct
19 Correct 183 ms 29804 KB Output is correct
20 Correct 184 ms 29784 KB Output is correct
21 Correct 279 ms 39084 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3452 KB Output is correct
2 Correct 23 ms 3408 KB Output is correct
3 Correct 223 ms 33024 KB Output is correct
4 Correct 221 ms 31544 KB Output is correct
5 Correct 228 ms 34552 KB Output is correct
6 Incorrect 278 ms 40596 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -