oj.uz

답안 #220126

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
220126 2020-04-07T05:43:52 Z IgorI 통행료 (IOI18_highway) C++17
69 / 100
 284 ms 40608 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) l--;
    if (s2 != Dist * a) l++;
    //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";


    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: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

# 결과 실행 시간 메모리 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 416 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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 20 ms 2920 KB Output is correct
3 Correct 187 ms 25820 KB Output is correct
4 Correct 194 ms 29104 KB Output is correct
5 Correct 198 ms 27956 KB Output is correct
6 Correct 187 ms 25404 KB Output is correct
7 Correct 187 ms 28012 KB Output is correct
8 Correct 185 ms 28240 KB Output is correct
9 Correct 178 ms 26200 KB Output is correct
10 Correct 189 ms 27624 KB Output is correct
11 Correct 225 ms 29348 KB Output is correct
12 Correct 221 ms 29444 KB Output is correct
13 Correct 206 ms 28572 KB Output is correct
14 Correct 227 ms 28216 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 3228 KB Output is correct
2 Correct 35 ms 6340 KB Output is correct
3 Correct 61 ms 9224 KB Output is correct
4 Correct 159 ms 29816 KB Output is correct
5 Correct 155 ms 30116 KB Output is correct
6 Correct 165 ms 29180 KB Output is correct
7 Correct 174 ms 27804 KB Output is correct
8 Correct 164 ms 29808 KB Output is correct
9 Correct 168 ms 28684 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 21 ms 3320 KB Output is correct
3 Correct 134 ms 20176 KB Output is correct
4 Correct 176 ms 26172 KB Output is correct
5 Correct 179 ms 25836 KB Output is correct
6 Correct 169 ms 25484 KB Output is correct
7 Correct 173 ms 24820 KB Output is correct
8 Correct 189 ms 25128 KB Output is correct
9 Correct 193 ms 27904 KB Output is correct
10 Correct 186 ms 27888 KB Output is correct
11 Correct 212 ms 28192 KB Output is correct
12 Correct 205 ms 29196 KB Output is correct
13 Correct 211 ms 28816 KB Output is correct
14 Correct 219 ms 28820 KB Output is correct
15 Correct 169 ms 25148 KB Output is correct
16 Correct 168 ms 25144 KB Output is correct
17 Correct 207 ms 28576 KB Output is correct
18 Correct 207 ms 28192 KB Output is correct
19 Correct 189 ms 24800 KB Output is correct
20 Correct 208 ms 29460 KB Output is correct
21 Correct 154 ms 25644 KB Output is correct
22 Correct 155 ms 24940 KB Output is correct
23 Correct 176 ms 30028 KB Output is correct
24 Correct 190 ms 29524 KB Output is correct
25 Correct 211 ms 28324 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 3424 KB Output is correct
2 Correct 23 ms 3528 KB Output is correct
3 Correct 215 ms 31668 KB Output is correct
4 Correct 258 ms 34104 KB Output is correct
5 Correct 279 ms 39504 KB Output is correct
6 Correct 264 ms 38880 KB Output is correct
7 Correct 282 ms 39388 KB Output is correct
8 Correct 284 ms 39400 KB Output is correct
9 Correct 193 ms 28084 KB Output is correct
10 Correct 161 ms 16760 KB Output is correct
11 Correct 216 ms 28148 KB Output is correct
12 Correct 246 ms 37340 KB Output is correct
13 Correct 266 ms 38128 KB Output is correct
14 Correct 277 ms 38896 KB Output is correct
15 Correct 269 ms 38564 KB Output is correct
16 Correct 221 ms 33748 KB Output is correct
17 Correct 170 ms 29032 KB Output is correct
18 Correct 176 ms 28576 KB Output is correct
19 Correct 186 ms 29660 KB Output is correct
20 Correct 190 ms 29764 KB Output is correct
21 Correct 274 ms 39088 KB Output is correct

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 3676 KB Output is correct
2 Correct 28 ms 3404 KB Output is correct
3 Correct 229 ms 32952 KB Output is correct
4 Correct 212 ms 31636 KB Output is correct
5 Correct 235 ms 34680 KB Output is correct
6 Incorrect 281 ms 40608 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -