oj.uz

Submission #599930

# Submission time Handle Problem Language Result Execution time Memory
599930 2022-07-20T09:39:56 Z MohamedFaresNebili Highway Tolls (IOI18_highway) C++14
100 / 100
 397 ms 27796 KB 
#include <bits/stdc++.h>
#include "highway.h"
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
 
                using namespace std;
 
                using ll = long long;
                using ld = long double;
                using ii = pair<ll, ll>;
                using vi = vector<int>;
 
                #define ff first
                #define ss second
                #define pb push_back
                #define all(x) (x).begin(), (x).end()
                #define lb lower_bound
 
                const int MOD = 1e9 + 7;
 
                int M, res = -1, D[100005][2];
				ll ST;
                vector<int> adj[100005];
                map<int, int> Key[100005];
 
                void BFS(int v, int state) {
                    queue<int> Q; Q.push(v); D[v][state] = 0;
                    while(!Q.empty()) {
                        int A = Q.front(); Q.pop();
                        for(auto u : adj[A]) {
                            if(D[u][state] > D[A][state] + 1) {
                                D[u][state] = D[A][state] + 1;
                                Q.push(u);
                            }
                        }
                    }
                }
                int solve(int v, int state) {
                    queue<int> Q; Q.push(v);
                    vector<int> E, dep(100005, -1);
                    vector<pair<int, int>> P;
                    dep[v] = 0;
                    while(!Q.empty()) {
                        int A = Q.front(); Q.pop();
                        for(auto u : adj[A]) {
                            int K = Key[A][u];
                            if(D[u][state] < D[u][1 - state]) {
                                if(dep[u] == -1) {
                                    dep[u] = dep[A] + 1;
                                    Q.push(u); P.push_back({K, u});
                                }
                                else if(dep[u] == dep[A] + 1)
                                    E.push_back(K);
                            }
                            else if(K != res) E.push_back(K);
                        }
                    }
                    if(P.empty()) return v;
                    int lo = 0, hi = P.size() - 1, C = -1;
                    vector<int> V(M, 0);
                    for(auto u : E) V[u] = 1;
                    reverse(P.begin(), P.end());
                    while(lo <= hi) {
                        int md = (lo + hi) / 2;
                        vector<int> R = V;
                        for(int l = 0; l <= md; l++)
                            R[P[l].ff] = 1;
                        if(ask(R) > ST)
                            C = md, hi = md - 1;
                        else lo = md + 1;
                    }
                    if(C == -1) return v;
                    return P[C].ss;
                }
 
                void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
                    M = U.size(); ST = ask(vector<int>(M, 0));
                    for(int l = 0; l < N; l++)
                        D[l][0] = D[l][1] = 1e9 + 7;
                    for(int l = 0; l < M; l++) {
                        int X = U[l], Y = V[l];
                        adj[X].push_back(Y);
                        adj[Y].push_back(X);
                        Key[X][Y] = Key[Y][X] = l;
                    }
                    int lo = 0, hi = M - 1;
                    while(lo <= hi) {
                        int md = (lo + hi) / 2;
                        vector<int> C(M, 0);
                        for(int l = 0; l <= md; l++) C[l] = 1;
                        ll E = ask(C);
                        if(E > ST) res = md, hi = md - 1;
                        else lo = md + 1;
                    }
                    int X = U[res], Y = V[res];
                    BFS(X, 0); BFS(Y, 1);
                    int S = solve(X, 0), T = solve(Y, 1);
                    answer(S, T);
                }

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7908 KB Output is correct
2 Correct 19 ms 9412 KB Output is correct
3 Correct 216 ms 22724 KB Output is correct
4 Correct 214 ms 22684 KB Output is correct
5 Correct 183 ms 22780 KB Output is correct
6 Correct 215 ms 22716 KB Output is correct
7 Correct 262 ms 22760 KB Output is correct
8 Correct 233 ms 22704 KB Output is correct
9 Correct 214 ms 22720 KB Output is correct
10 Correct 216 ms 22680 KB Output is correct
11 Correct 245 ms 22292 KB Output is correct
12 Correct 273 ms 22560 KB Output is correct
13 Correct 219 ms 22548 KB Output is correct
14 Correct 252 ms 22656 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9376 KB Output is correct
2 Correct 35 ms 11084 KB Output is correct
3 Correct 52 ms 12636 KB Output is correct
4 Correct 111 ms 22432 KB Output is correct
5 Correct 114 ms 22516 KB Output is correct
6 Correct 131 ms 22764 KB Output is correct
7 Correct 148 ms 22580 KB Output is correct
8 Correct 132 ms 22328 KB Output is correct
9 Correct 108 ms 22552 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7888 KB Output is correct
2 Correct 23 ms 9380 KB Output is correct
3 Correct 170 ms 19724 KB Output is correct
4 Correct 190 ms 22780 KB Output is correct
5 Correct 201 ms 22788 KB Output is correct
6 Correct 233 ms 22772 KB Output is correct
7 Correct 194 ms 22772 KB Output is correct
8 Correct 225 ms 22660 KB Output is correct
9 Correct 213 ms 22772 KB Output is correct
10 Correct 248 ms 22716 KB Output is correct
11 Correct 228 ms 22796 KB Output is correct
12 Correct 206 ms 22620 KB Output is correct
13 Correct 222 ms 22616 KB Output is correct
14 Correct 214 ms 22336 KB Output is correct
15 Correct 263 ms 22748 KB Output is correct
16 Correct 209 ms 22792 KB Output is correct
17 Correct 227 ms 22740 KB Output is correct
18 Correct 230 ms 22608 KB Output is correct
19 Correct 219 ms 22752 KB Output is correct
20 Correct 194 ms 22636 KB Output is correct
21 Correct 255 ms 23264 KB Output is correct
22 Correct 262 ms 23264 KB Output is correct
23 Correct 269 ms 22780 KB Output is correct
24 Correct 237 ms 22772 KB Output is correct
25 Correct 213 ms 22704 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 9500 KB Output is correct
2 Correct 31 ms 9604 KB Output is correct
3 Correct 226 ms 24024 KB Output is correct
4 Correct 291 ms 25036 KB Output is correct
5 Correct 324 ms 27796 KB Output is correct
6 Correct 309 ms 27616 KB Output is correct
7 Correct 347 ms 27524 KB Output is correct
8 Correct 321 ms 27456 KB Output is correct
9 Correct 392 ms 26164 KB Output is correct
10 Correct 393 ms 27100 KB Output is correct
11 Correct 338 ms 26136 KB Output is correct
12 Correct 315 ms 27160 KB Output is correct
13 Correct 332 ms 27548 KB Output is correct
14 Correct 336 ms 27360 KB Output is correct
15 Correct 336 ms 27604 KB Output is correct
16 Correct 294 ms 26552 KB Output is correct
17 Correct 251 ms 23344 KB Output is correct
18 Correct 233 ms 23480 KB Output is correct
19 Correct 236 ms 23548 KB Output is correct
20 Correct 239 ms 23572 KB Output is correct
21 Correct 341 ms 27496 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 9424 KB Output is correct
2 Correct 23 ms 9620 KB Output is correct
3 Correct 251 ms 23852 KB Output is correct
4 Correct 241 ms 24340 KB Output is correct
5 Correct 245 ms 25124 KB Output is correct
6 Correct 289 ms 27420 KB Output is correct
7 Correct 229 ms 24116 KB Output is correct
8 Correct 229 ms 24560 KB Output is correct
9 Correct 280 ms 24876 KB Output is correct
10 Correct 297 ms 27504 KB Output is correct
11 Correct 335 ms 27632 KB Output is correct
12 Correct 343 ms 27556 KB Output is correct
13 Correct 364 ms 26784 KB Output is correct
14 Correct 313 ms 26648 KB Output is correct
15 Correct 338 ms 26684 KB Output is correct
16 Correct 325 ms 26716 KB Output is correct
17 Correct 373 ms 26700 KB Output is correct
18 Correct 397 ms 27028 KB Output is correct
19 Correct 301 ms 27008 KB Output is correct
20 Correct 302 ms 27240 KB Output is correct
21 Correct 347 ms 27352 KB Output is correct
22 Correct 295 ms 27312 KB Output is correct
23 Correct 299 ms 27692 KB Output is correct
24 Correct 340 ms 27312 KB Output is correct
25 Correct 308 ms 27424 KB Output is correct
26 Correct 315 ms 27408 KB Output is correct
27 Correct 212 ms 23348 KB Output is correct
28 Correct 237 ms 23416 KB Output is correct
29 Correct 203 ms 23788 KB Output is correct
30 Correct 256 ms 23656 KB Output is correct
31 Correct 254 ms 23440 KB Output is correct
32 Correct 273 ms 23356 KB Output is correct
33 Correct 240 ms 23720 KB Output is correct
34 Correct 213 ms 23432 KB Output is correct
35 Correct 268 ms 23368 KB Output is correct
36 Correct 238 ms 23408 KB Output is correct
37 Correct 226 ms 23644 KB Output is correct
38 Correct 285 ms 23932 KB Output is correct
39 Correct 350 ms 27452 KB Output is correct
40 Correct 338 ms 27492 KB Output is correct
41 Correct 270 ms 27732 KB Output is correct
42 Correct 384 ms 27444 KB Output is correct