oj.uz

Submission #530087

# Submission time Handle Problem Language Result Execution time Memory
530087 2022-02-24T14:41:36 Z qwerasdfzxcl Highway Tolls (IOI18_highway) C++14
100 / 100
 273 ms 17460 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;
        if (l==1 && r>=60000) m = mx - 30000;
        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);

    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 4 ms 4936 KB Output is correct
5 Correct 3 ms 5004 KB Output is correct
6 Correct 3 ms 5004 KB Output is correct
7 Correct 3 ms 5004 KB Output is correct
8 Correct 3 ms 5000 KB Output is correct
9 Correct 3 ms 5000 KB Output is correct
10 Correct 2 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 3 ms 5076 KB Output is correct
2 Correct 14 ms 6088 KB Output is correct
3 Correct 151 ms 14676 KB Output is correct
4 Correct 185 ms 14672 KB Output is correct
5 Correct 144 ms 14684 KB Output is correct
6 Correct 131 ms 14664 KB Output is correct
7 Correct 137 ms 14716 KB Output is correct
8 Correct 174 ms 14672 KB Output is correct
9 Correct 198 ms 14696 KB Output is correct
10 Correct 130 ms 14684 KB Output is correct
11 Correct 160 ms 14620 KB Output is correct
12 Correct 143 ms 15028 KB Output is correct
13 Correct 183 ms 14744 KB Output is correct
14 Correct 177 ms 14268 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 26 ms 7496 KB Output is correct
3 Correct 37 ms 6812 KB Output is correct
4 Correct 111 ms 14640 KB Output is correct
5 Correct 98 ms 14736 KB Output is correct
6 Correct 93 ms 16252 KB Output is correct
7 Correct 141 ms 10032 KB Output is correct
8 Correct 134 ms 15368 KB Output is correct
9 Correct 121 ms 11704 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5064 KB Output is correct
2 Correct 19 ms 5968 KB Output is correct
3 Correct 100 ms 11072 KB Output is correct
4 Correct 161 ms 11560 KB Output is correct
5 Correct 187 ms 13300 KB Output is correct
6 Correct 144 ms 10280 KB Output is correct
7 Correct 129 ms 12168 KB Output is correct
8 Correct 152 ms 11572 KB Output is correct
9 Correct 173 ms 13856 KB Output is correct
10 Correct 161 ms 14620 KB Output is correct
11 Correct 113 ms 11324 KB Output is correct
12 Correct 148 ms 13676 KB Output is correct
13 Correct 178 ms 13268 KB Output is correct
14 Correct 184 ms 13740 KB Output is correct
15 Correct 175 ms 13452 KB Output is correct
16 Correct 117 ms 11396 KB Output is correct
17 Correct 139 ms 13040 KB Output is correct
18 Correct 119 ms 11244 KB Output is correct
19 Correct 118 ms 10220 KB Output is correct
20 Correct 117 ms 10152 KB Output is correct
21 Correct 166 ms 13988 KB Output is correct
22 Correct 173 ms 12676 KB Output is correct
23 Correct 169 ms 15172 KB Output is correct
24 Correct 164 ms 15384 KB Output is correct
25 Correct 178 ms 17460 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5960 KB Output is correct
2 Correct 24 ms 6080 KB Output is correct
3 Correct 206 ms 14756 KB Output is correct
4 Correct 221 ms 14496 KB Output is correct
5 Correct 240 ms 15876 KB Output is correct
6 Correct 273 ms 15336 KB Output is correct
7 Correct 270 ms 15632 KB Output is correct
8 Correct 273 ms 15936 KB Output is correct
9 Correct 200 ms 11104 KB Output is correct
10 Correct 151 ms 11320 KB Output is correct
11 Correct 215 ms 11276 KB Output is correct
12 Correct 256 ms 14348 KB Output is correct
13 Correct 195 ms 15380 KB Output is correct
14 Correct 224 ms 15480 KB Output is correct
15 Correct 218 ms 15704 KB Output is correct
16 Correct 232 ms 13088 KB Output is correct
17 Correct 173 ms 14768 KB Output is correct
18 Correct 131 ms 14268 KB Output is correct
19 Correct 125 ms 15248 KB Output is correct
20 Correct 134 ms 13200 KB Output is correct
21 Correct 206 ms 16264 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 26 ms 5952 KB Output is correct
3 Correct 168 ms 14132 KB Output is correct
4 Correct 202 ms 14848 KB Output is correct
5 Correct 180 ms 14388 KB Output is correct
6 Correct 272 ms 15968 KB Output is correct
7 Correct 203 ms 14484 KB Output is correct
8 Correct 191 ms 15112 KB Output is correct
9 Correct 173 ms 15460 KB Output is correct
10 Correct 268 ms 16072 KB Output is correct
11 Correct 219 ms 15524 KB Output is correct
12 Correct 215 ms 16108 KB Output is correct
13 Correct 153 ms 11624 KB Output is correct
14 Correct 192 ms 12212 KB Output is correct
15 Correct 207 ms 12136 KB Output is correct
16 Correct 181 ms 11876 KB Output is correct
17 Correct 138 ms 11124 KB Output is correct
18 Correct 132 ms 12164 KB Output is correct
19 Correct 201 ms 14580 KB Output is correct
20 Correct 196 ms 15016 KB Output is correct
21 Correct 216 ms 15284 KB Output is correct
22 Correct 255 ms 15084 KB Output is correct
23 Correct 207 ms 15812 KB Output is correct
24 Correct 219 ms 15692 KB Output is correct
25 Correct 211 ms 13904 KB Output is correct
26 Correct 243 ms 15880 KB Output is correct
27 Correct 148 ms 13768 KB Output is correct
28 Correct 165 ms 13792 KB Output is correct
29 Correct 140 ms 13276 KB Output is correct
30 Correct 149 ms 12500 KB Output is correct
31 Correct 153 ms 13864 KB Output is correct
32 Correct 152 ms 12880 KB Output is correct
33 Correct 134 ms 14016 KB Output is correct
34 Correct 130 ms 15300 KB Output is correct
35 Correct 154 ms 15636 KB Output is correct
36 Correct 170 ms 13556 KB Output is correct
37 Correct 168 ms 13220 KB Output is correct
38 Correct 184 ms 13084 KB Output is correct
39 Correct 267 ms 16580 KB Output is correct
40 Correct 257 ms 16612 KB Output is correct
41 Correct 210 ms 16144 KB Output is correct
42 Correct 205 ms 16216 KB Output is correct