oj.uz

Submission #838140

# Submission time Handle Problem Language Result Execution time Memory
838140 2023-08-26T09:22:00 Z becaido Highway Tolls (IOI18_highway) C++17
100 / 100
 188 ms 12148 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for(int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1.3e5 + 5;

ll len;
vector<pair<int, int>> adj[SIZE], all[2];
vector<int> e;
int g[SIZE];
bool is[SIZE];

int cal(int s, int M) {
    int sz = all[s].size();
    int l = 0, r = sz - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        FOR (i, 0, M - 1) e[i] = !is[i];
        FOR (i, mid + 1, sz - 1) e[all[s][i].S] = 1;
        if (ask(e) == len) r = mid;
        else l = mid + 1;
    }
    return all[s][l].F;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int M = U.size();
    e.resize(M, 0);
    FOR (i, 0, M - 1) {
        adj[U[i]].pb(V[i], i);
        adj[V[i]].pb(U[i], i);
    }
    len = ask(e);
    int l = 0, r = M - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        fill(e.begin(), e.end(), 0);
        fill(e.begin(), e.begin() + mid + 1, 1);
        if (ask(e) == len) l = mid + 1;
        else r = mid;
    }
    queue<int> q;
    is[l] = 1;
    fill(g, g + N, -1);
    q.push(U[l]), g[U[l]] = 0, all[0].pb(U[l], -1);
    q.push(V[l]), g[V[l]] = 1, all[1].pb(V[l], -1);
    while (q.size()) {
        int pos = q.front();
        q.pop();
        for (auto [np, id] : adj[pos]) if (g[np] == -1) {
            g[np] = g[pos];
            is[id] = 1;
            all[g[pos]].pb(np, id);
            q.push(np);
        }
    }
    answer(cal(0, M), cal(1, M));
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3280 KB Output is correct
2 Correct 2 ms 3280 KB Output is correct
3 Correct 2 ms 3280 KB Output is correct
4 Correct 2 ms 3280 KB Output is correct
5 Correct 2 ms 3280 KB Output is correct
6 Correct 2 ms 3360 KB Output is correct
7 Correct 2 ms 3280 KB Output is correct
8 Correct 2 ms 3280 KB Output is correct
9 Correct 2 ms 3280 KB Output is correct
10 Correct 2 ms 3280 KB Output is correct
11 Correct 2 ms 3280 KB Output is correct
12 Correct 2 ms 3280 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3408 KB Output is correct
2 Correct 12 ms 4176 KB Output is correct
3 Correct 116 ms 10048 KB Output is correct
4 Correct 120 ms 10084 KB Output is correct
5 Correct 78 ms 10056 KB Output is correct
6 Correct 77 ms 10044 KB Output is correct
7 Correct 77 ms 10088 KB Output is correct
8 Correct 121 ms 10076 KB Output is correct
9 Correct 85 ms 10068 KB Output is correct
10 Correct 120 ms 10048 KB Output is correct
11 Correct 86 ms 9492 KB Output is correct
12 Correct 125 ms 9820 KB Output is correct
13 Correct 90 ms 9536 KB Output is correct
14 Correct 77 ms 9580 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4148 KB Output is correct
2 Correct 19 ms 4764 KB Output is correct
3 Correct 26 ms 5400 KB Output is correct
4 Correct 79 ms 9300 KB Output is correct
5 Correct 99 ms 9300 KB Output is correct
6 Correct 77 ms 9708 KB Output is correct
7 Correct 85 ms 9576 KB Output is correct
8 Correct 75 ms 9296 KB Output is correct
9 Correct 61 ms 9748 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 13 ms 4144 KB Output is correct
3 Correct 55 ms 8792 KB Output is correct
4 Correct 105 ms 10064 KB Output is correct
5 Correct 82 ms 10028 KB Output is correct
6 Correct 71 ms 10128 KB Output is correct
7 Correct 75 ms 10076 KB Output is correct
8 Correct 81 ms 10024 KB Output is correct
9 Correct 104 ms 10116 KB Output is correct
10 Correct 78 ms 10060 KB Output is correct
11 Correct 100 ms 9500 KB Output is correct
12 Correct 78 ms 9624 KB Output is correct
13 Correct 98 ms 9716 KB Output is correct
14 Correct 111 ms 9224 KB Output is correct
15 Correct 79 ms 10076 KB Output is correct
16 Correct 95 ms 10052 KB Output is correct
17 Correct 81 ms 9664 KB Output is correct
18 Correct 76 ms 9552 KB Output is correct
19 Correct 71 ms 10024 KB Output is correct
20 Correct 85 ms 9464 KB Output is correct
21 Correct 64 ms 10936 KB Output is correct
22 Correct 96 ms 10808 KB Output is correct
23 Correct 105 ms 10412 KB Output is correct
24 Correct 82 ms 10264 KB Output is correct
25 Correct 91 ms 9676 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4048 KB Output is correct
2 Correct 13 ms 4176 KB Output is correct
3 Correct 128 ms 10432 KB Output is correct
4 Correct 106 ms 10988 KB Output is correct
5 Correct 127 ms 12036 KB Output is correct
6 Correct 126 ms 11608 KB Output is correct
7 Correct 130 ms 11656 KB Output is correct
8 Correct 160 ms 11696 KB Output is correct
9 Correct 127 ms 9492 KB Output is correct
10 Correct 120 ms 9920 KB Output is correct
11 Correct 147 ms 10560 KB Output is correct
12 Correct 121 ms 11452 KB Output is correct
13 Correct 157 ms 11664 KB Output is correct
14 Correct 133 ms 11816 KB Output is correct
15 Correct 162 ms 12084 KB Output is correct
16 Correct 153 ms 10604 KB Output is correct
17 Correct 91 ms 10568 KB Output is correct
18 Correct 89 ms 10632 KB Output is correct
19 Correct 103 ms 10572 KB Output is correct
20 Correct 79 ms 10796 KB Output is correct
21 Correct 132 ms 11996 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4076 KB Output is correct
2 Correct 13 ms 4176 KB Output is correct
3 Correct 118 ms 10372 KB Output is correct
4 Correct 133 ms 10580 KB Output is correct
5 Correct 102 ms 10724 KB Output is correct
6 Correct 154 ms 11684 KB Output is correct
7 Correct 118 ms 10436 KB Output is correct
8 Correct 116 ms 10672 KB Output is correct
9 Correct 103 ms 10708 KB Output is correct
10 Correct 160 ms 11720 KB Output is correct
11 Correct 188 ms 11912 KB Output is correct
12 Correct 145 ms 11596 KB Output is correct
13 Correct 87 ms 10444 KB Output is correct
14 Correct 84 ms 9908 KB Output is correct
15 Correct 117 ms 10484 KB Output is correct
16 Correct 114 ms 9916 KB Output is correct
17 Correct 132 ms 10432 KB Output is correct
18 Correct 172 ms 9988 KB Output is correct
19 Correct 152 ms 11292 KB Output is correct
20 Correct 141 ms 11792 KB Output is correct
21 Correct 123 ms 11820 KB Output is correct
22 Correct 164 ms 11656 KB Output is correct
23 Correct 141 ms 11744 KB Output is correct
24 Correct 141 ms 11676 KB Output is correct
25 Correct 121 ms 12148 KB Output is correct
26 Correct 115 ms 12076 KB Output is correct
27 Correct 109 ms 10644 KB Output is correct
28 Correct 75 ms 10488 KB Output is correct
29 Correct 72 ms 10672 KB Output is correct
30 Correct 77 ms 10488 KB Output is correct
31 Correct 92 ms 10508 KB Output is correct
32 Correct 124 ms 10484 KB Output is correct
33 Correct 95 ms 10704 KB Output is correct
34 Correct 108 ms 10492 KB Output is correct
35 Correct 94 ms 10572 KB Output is correct
36 Correct 75 ms 10468 KB Output is correct
37 Correct 84 ms 10636 KB Output is correct
38 Correct 74 ms 10664 KB Output is correct
39 Correct 142 ms 12136 KB Output is correct
40 Correct 124 ms 12148 KB Output is correct
41 Correct 123 ms 11948 KB Output is correct
42 Correct 119 ms 11628 KB Output is correct