oj.uz

Submission #220119

# Submission time Handle Problem Language Result Execution time Memory
220119 2020-04-07T05:26:16 Z IgorI Highway Tolls (IOI18_highway) C++17
69 / 100
 303 ms 15936 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;
}

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 = ask(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
    return kek[l].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 = ask(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 = ask(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";
    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:54: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:58: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:139:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < qV.size(); i++)
                     ~~^~~~~~~~~~~
highway.cpp:154: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 512 KB Output is correct
2 Correct 18 ms 1920 KB Output is correct
3 Correct 193 ms 14160 KB Output is correct
4 Correct 190 ms 14008 KB Output is correct
5 Correct 183 ms 13952 KB Output is correct
6 Correct 185 ms 14004 KB Output is correct
7 Correct 190 ms 14204 KB Output is correct
8 Correct 164 ms 14088 KB Output is correct
9 Correct 170 ms 14168 KB Output is correct
10 Correct 177 ms 14096 KB Output is correct
11 Correct 203 ms 13060 KB Output is correct
12 Correct 192 ms 13908 KB Output is correct
13 Correct 194 ms 13792 KB Output is correct
14 Correct 216 ms 13920 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1920 KB Output is correct
2 Correct 36 ms 3276 KB Output is correct
3 Correct 46 ms 4636 KB Output is correct
4 Correct 146 ms 13244 KB Output is correct
5 Correct 146 ms 13260 KB Output is correct
6 Correct 137 ms 14108 KB Output is correct
7 Correct 135 ms 13920 KB Output is correct
8 Correct 158 ms 13172 KB Output is correct
9 Correct 133 ms 13800 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 21 ms 1932 KB Output is correct
3 Correct 132 ms 11468 KB Output is correct
4 Correct 193 ms 13980 KB Output is correct
5 Correct 193 ms 13992 KB Output is correct
6 Correct 170 ms 14100 KB Output is correct
7 Correct 172 ms 14172 KB Output is correct
8 Correct 179 ms 14016 KB Output is correct
9 Correct 185 ms 13964 KB Output is correct
10 Correct 192 ms 14056 KB Output is correct
11 Correct 206 ms 13904 KB Output is correct
12 Correct 209 ms 13848 KB Output is correct
13 Correct 217 ms 13928 KB Output is correct
14 Correct 209 ms 12904 KB Output is correct
15 Correct 223 ms 14020 KB Output is correct
16 Correct 187 ms 14096 KB Output is correct
17 Correct 212 ms 13796 KB Output is correct
18 Correct 205 ms 13920 KB Output is correct
19 Correct 175 ms 14092 KB Output is correct
20 Correct 231 ms 13924 KB Output is correct
21 Correct 145 ms 14376 KB Output is correct
22 Correct 132 ms 14276 KB Output is correct
23 Correct 152 ms 13464 KB Output is correct
24 Correct 165 ms 13304 KB Output is correct
25 Correct 202 ms 13988 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2048 KB Output is correct
2 Correct 26 ms 2048 KB Output is correct
3 Correct 214 ms 14624 KB Output is correct
4 Correct 246 ms 13960 KB Output is correct
5 Correct 303 ms 14672 KB Output is correct
6 Correct 287 ms 15936 KB Output is correct
7 Correct 263 ms 15624 KB Output is correct
8 Correct 272 ms 14616 KB Output is correct
9 Correct 179 ms 9156 KB Output is correct
10 Correct 153 ms 7424 KB Output is correct
11 Correct 179 ms 10408 KB Output is correct
12 Correct 246 ms 13152 KB Output is correct
13 Correct 274 ms 14700 KB Output is correct
14 Correct 270 ms 14424 KB Output is correct
15 Correct 286 ms 14608 KB Output is correct
16 Correct 219 ms 10108 KB Output is correct
17 Correct 147 ms 14296 KB Output is correct
18 Correct 177 ms 14420 KB Output is correct
19 Correct 171 ms 14444 KB Output is correct
20 Correct 160 ms 14484 KB Output is correct
21 Correct 256 ms 15576 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1888 KB Output is correct
2 Correct 26 ms 2040 KB Output is correct
3 Correct 223 ms 13812 KB Output is correct
4 Correct 202 ms 14760 KB Output is correct
5 Correct 217 ms 14888 KB Output is correct
6 Incorrect 266 ms 14624 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -