oj.uz

Submission #530077

# Submission time Handle Problem Language Result Execution time Memory
530077 2022-02-24T13:58:55 Z qwerasdfzxcl Highway Tolls (IOI18_highway) C++14
100 / 100
 271 ms 17356 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<pair<int, int>> adj[100100], G[100100];
vector<int> w, rans;
int n, m, a, b, P[100100], E[100100], par[100100], cnt = -1;
ll c0;

ll myask(vector<int> &w){
    return ask(w);
}

int search1(){
    int l = 0, r = n-1, ans = -1;
    while(l<=r){
        int m = (l+r)>>1;
        if (l==0 && r>=60000) m = 30000;
        fill(w.begin(), w.end(), 0);
        for (int i=0;i<=m;i++) for (auto &[v, j]:adj[i]) w[j] = 1;

        if (myask(w)==c0) ans = m, l = m+1;
        else r = m-1;
    }

    fill(w.begin(), w.end(), 0);
    for (int i=0;i<=ans;i++) for (auto &[v, j]:adj[i]) w[j] = 1;
    return ans + 1;
}

bool visited[100100];
void bfs(int s){
    queue<int> q;
    q.push(s);
    visited[s] = 1;
    while(!q.empty()){
        int cur = q.front(); q.pop();
        for (auto &[nxt, i]:adj[cur]) if (!w[i] && !visited[nxt]){
            G[cur].emplace_back(nxt, i);
            G[nxt].emplace_back(cur, i);
            visited[nxt] = 1;
            w[i] = -1;
            q.push(nxt);
        }
    }
}

void dfs(int s, int pa = -1, int idx = -1, int val = 0){
    P[++cnt] = s;
    E[cnt] = idx;
    par[cnt] = val;

    int tmp = cnt;
    for (auto &[v, i]:G[s]) if (v!=pa){
        dfs(v, s, i, tmp);
    }
}

int search2(int mx){
    int l = 1, r = mx, ans = mx+1;
    while(l<=r){
        int m = (l+r)>>1;
        for (int i=1;i<=cnt;i++) w[E[i]] = 0;
        for (int i=m;i<=mx;i++) w[E[i]] = 1;

        if (myask(w)==c0) ans = m, r = m-1;
        else l = m+1;
    }
    rans.push_back(P[--ans]);

    if (ans==0) return 0;
    for(;par[ans];ans=par[ans]);
    //printf("ret: %d\n", ans);
    return ans;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    n = N, a = A, b = B, m = U.size();
    for (int i=0;i<m;i++){
        adj[U[i]].emplace_back(V[i], i);
        adj[V[i]].emplace_back(U[i], i);
    }

    w.resize(m);
    c0 = myask(w);

    int x = search1();
    bfs(x);
    for (int i=0;i<m;i++){
        if (w[i]==-1) w[i] = 0;
        else w[i] = 1;
    }
    dfs(x);

    /*printf("x: %d\n", x);
    printf("E: ");
    for (int i=0;i<=cnt;i++) printf("%d ", E[i]);
    printf("\nP: ");
    for (int i=0;i<=cnt;i++) printf("%d ", P[i]);
    printf("\npar: ");
    for (int i=0;i<=cnt;i++) printf("%d ", par[i]);
    printf("\n");*/

    search2(search2(cnt)-1);
    answer(rans[0], rans[1]);
}

Compilation message

highway.cpp: In function 'int search1()':
highway.cpp:21:43: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |         for (int i=0;i<=m;i++) for (auto &[v, j]:adj[i]) w[j] = 1;
      |                                           ^
highway.cpp:28:41: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |     for (int i=0;i<=ans;i++) for (auto &[v, j]:adj[i]) w[j] = 1;
      |                                         ^
highway.cpp: In function 'void bfs(int)':
highway.cpp:39:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |         for (auto &[nxt, i]:adj[cur]) if (!w[i] && !visited[nxt]){
      |                    ^
highway.cpp: In function 'void dfs(int, int, int, int)':
highway.cpp:55:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for (auto &[v, i]:G[s]) if (v!=pa){
      |                ^

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5064 KB Output is correct
2 Correct 15 ms 5960 KB Output is correct
3 Correct 136 ms 14688 KB Output is correct
4 Correct 140 ms 14660 KB Output is correct
5 Correct 138 ms 14760 KB Output is correct
6 Correct 167 ms 14668 KB Output is correct
7 Correct 146 ms 14688 KB Output is correct
8 Correct 141 ms 14676 KB Output is correct
9 Correct 134 ms 14672 KB Output is correct
10 Correct 155 ms 14852 KB Output is correct
11 Correct 144 ms 14588 KB Output is correct
12 Correct 180 ms 15020 KB Output is correct
13 Correct 170 ms 14676 KB Output is correct
14 Correct 180 ms 14296 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6216 KB Output is correct
2 Correct 22 ms 7448 KB Output is correct
3 Correct 46 ms 6852 KB Output is correct
4 Correct 107 ms 14648 KB Output is correct
5 Correct 107 ms 14884 KB Output is correct
6 Correct 94 ms 16144 KB Output is correct
7 Correct 93 ms 10024 KB Output is correct
8 Correct 140 ms 15404 KB Output is correct
9 Correct 97 ms 11712 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5064 KB Output is correct
2 Correct 16 ms 5956 KB Output is correct
3 Correct 125 ms 11072 KB Output is correct
4 Correct 129 ms 11584 KB Output is correct
5 Correct 124 ms 13312 KB Output is correct
6 Correct 99 ms 10276 KB Output is correct
7 Correct 158 ms 12320 KB Output is correct
8 Correct 124 ms 11572 KB Output is correct
9 Correct 180 ms 13860 KB Output is correct
10 Correct 168 ms 14484 KB Output is correct
11 Correct 151 ms 11412 KB Output is correct
12 Correct 150 ms 13680 KB Output is correct
13 Correct 176 ms 13276 KB Output is correct
14 Correct 172 ms 13644 KB Output is correct
15 Correct 169 ms 13460 KB Output is correct
16 Correct 151 ms 11380 KB Output is correct
17 Correct 157 ms 13096 KB Output is correct
18 Correct 121 ms 11200 KB Output is correct
19 Correct 97 ms 10236 KB Output is correct
20 Correct 140 ms 10152 KB Output is correct
21 Correct 167 ms 13960 KB Output is correct
22 Correct 164 ms 12676 KB Output is correct
23 Correct 124 ms 15172 KB Output is correct
24 Correct 158 ms 15436 KB Output is correct
25 Correct 176 ms 17356 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5988 KB Output is correct
2 Correct 24 ms 6088 KB Output is correct
3 Correct 163 ms 14672 KB Output is correct
4 Correct 175 ms 14560 KB Output is correct
5 Correct 260 ms 15736 KB Output is correct
6 Correct 263 ms 15360 KB Output is correct
7 Correct 205 ms 15752 KB Output is correct
8 Correct 211 ms 15980 KB Output is correct
9 Correct 199 ms 11116 KB Output is correct
10 Correct 176 ms 11296 KB Output is correct
11 Correct 171 ms 11228 KB Output is correct
12 Correct 188 ms 14264 KB Output is correct
13 Correct 194 ms 15392 KB Output is correct
14 Correct 223 ms 15496 KB Output is correct
15 Correct 251 ms 15628 KB Output is correct
16 Correct 178 ms 13084 KB Output is correct
17 Correct 133 ms 14772 KB Output is correct
18 Correct 144 ms 14288 KB Output is correct
19 Correct 134 ms 15256 KB Output is correct
20 Correct 161 ms 13196 KB Output is correct
21 Correct 218 ms 16256 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6080 KB Output is correct
2 Correct 19 ms 5976 KB Output is correct
3 Correct 162 ms 14092 KB Output is correct
4 Correct 173 ms 14796 KB Output is correct
5 Correct 226 ms 14348 KB Output is correct
6 Correct 222 ms 15956 KB Output is correct
7 Correct 174 ms 14360 KB Output is correct
8 Correct 199 ms 15112 KB Output is correct
9 Correct 190 ms 15304 KB Output is correct
10 Correct 215 ms 16072 KB Output is correct
11 Correct 267 ms 15476 KB Output is correct
12 Correct 249 ms 16112 KB Output is correct
13 Correct 210 ms 11668 KB Output is correct
14 Correct 181 ms 12212 KB Output is correct
15 Correct 207 ms 12136 KB Output is correct
16 Correct 152 ms 11892 KB Output is correct
17 Correct 170 ms 11112 KB Output is correct
18 Correct 157 ms 12116 KB Output is correct
19 Correct 187 ms 14588 KB Output is correct
20 Correct 248 ms 15024 KB Output is correct
21 Correct 216 ms 15220 KB Output is correct
22 Correct 262 ms 15124 KB Output is correct
23 Correct 225 ms 15792 KB Output is correct
24 Correct 271 ms 15624 KB Output is correct
25 Correct 240 ms 13904 KB Output is correct
26 Correct 253 ms 15952 KB Output is correct
27 Correct 134 ms 13644 KB Output is correct
28 Correct 119 ms 13804 KB Output is correct
29 Correct 145 ms 13176 KB Output is correct
30 Correct 172 ms 12568 KB Output is correct
31 Correct 126 ms 13864 KB Output is correct
32 Correct 174 ms 13004 KB Output is correct
33 Correct 136 ms 14024 KB Output is correct
34 Correct 128 ms 15308 KB Output is correct
35 Correct 132 ms 15596 KB Output is correct
36 Correct 162 ms 13560 KB Output is correct
37 Correct 135 ms 13312 KB Output is correct
38 Correct 147 ms 13092 KB Output is correct
39 Correct 257 ms 16588 KB Output is correct
40 Correct 191 ms 16608 KB Output is correct
41 Correct 218 ms 16140 KB Output is correct
42 Correct 265 ms 16140 KB Output is correct