oj.uz

Submission #599935

# Submission time Handle Problem Language Result Execution time Memory
599935 2022-07-20T09:46:07 Z MohamedFaresNebili Highway Tolls (IOI18_highway) C++14
100 / 100
 388 ms 27720 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 7732 KB Output is correct
2 Correct 5 ms 7732 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 7760 KB Output is correct
6 Correct 4 ms 7760 KB Output is correct
7 Correct 4 ms 7736 KB Output is correct
8 Correct 4 ms 7736 KB Output is correct
9 Correct 5 ms 7760 KB Output is correct
10 Correct 4 ms 7716 KB Output is correct
11 Correct 4 ms 7760 KB Output is correct
12 Correct 4 ms 7760 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7892 KB Output is correct
2 Correct 18 ms 9380 KB Output is correct
3 Correct 198 ms 22744 KB Output is correct
4 Correct 206 ms 22792 KB Output is correct
5 Correct 233 ms 22776 KB Output is correct
6 Correct 224 ms 22764 KB Output is correct
7 Correct 246 ms 22776 KB Output is correct
8 Correct 197 ms 22688 KB Output is correct
9 Correct 243 ms 22840 KB Output is correct
10 Correct 181 ms 22712 KB Output is correct
11 Correct 204 ms 22296 KB Output is correct
12 Correct 196 ms 22744 KB Output is correct
13 Correct 209 ms 22576 KB Output is correct
14 Correct 253 ms 22620 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 9416 KB Output is correct
2 Correct 27 ms 11048 KB Output is correct
3 Correct 35 ms 12640 KB Output is correct
4 Correct 116 ms 22428 KB Output is correct
5 Correct 148 ms 22432 KB Output is correct
6 Correct 115 ms 22712 KB Output is correct
7 Correct 159 ms 22644 KB Output is correct
8 Correct 161 ms 22340 KB Output is correct
9 Correct 145 ms 22556 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7856 KB Output is correct
2 Correct 23 ms 9368 KB Output is correct
3 Correct 218 ms 19796 KB Output is correct
4 Correct 233 ms 22680 KB Output is correct
5 Correct 247 ms 22784 KB Output is correct
6 Correct 214 ms 22780 KB Output is correct
7 Correct 220 ms 22764 KB Output is correct
8 Correct 210 ms 22696 KB Output is correct
9 Correct 212 ms 22740 KB Output is correct
10 Correct 243 ms 22772 KB Output is correct
11 Correct 225 ms 22608 KB Output is correct
12 Correct 219 ms 22664 KB Output is correct
13 Correct 242 ms 22660 KB Output is correct
14 Correct 232 ms 22336 KB Output is correct
15 Correct 217 ms 22812 KB Output is correct
16 Correct 239 ms 22692 KB Output is correct
17 Correct 239 ms 22640 KB Output is correct
18 Correct 236 ms 22612 KB Output is correct
19 Correct 244 ms 22776 KB Output is correct
20 Correct 201 ms 22660 KB Output is correct
21 Correct 220 ms 23268 KB Output is correct
22 Correct 251 ms 23288 KB Output is correct
23 Correct 234 ms 22756 KB Output is correct
24 Correct 227 ms 23056 KB Output is correct
25 Correct 228 ms 22644 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 9476 KB Output is correct
2 Correct 28 ms 9612 KB Output is correct
3 Correct 217 ms 23928 KB Output is correct
4 Correct 278 ms 25084 KB Output is correct
5 Correct 351 ms 27712 KB Output is correct
6 Correct 299 ms 27620 KB Output is correct
7 Correct 293 ms 27636 KB Output is correct
8 Correct 296 ms 27416 KB Output is correct
9 Correct 333 ms 26164 KB Output is correct
10 Correct 347 ms 27012 KB Output is correct
11 Correct 388 ms 26172 KB Output is correct
12 Correct 355 ms 27252 KB Output is correct
13 Correct 314 ms 27644 KB Output is correct
14 Correct 303 ms 27392 KB Output is correct
15 Correct 364 ms 27600 KB Output is correct
16 Correct 293 ms 26548 KB Output is correct
17 Correct 276 ms 23392 KB Output is correct
18 Correct 243 ms 23400 KB Output is correct
19 Correct 248 ms 23456 KB Output is correct
20 Correct 238 ms 23580 KB Output is correct
21 Correct 353 ms 27480 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 9512 KB Output is correct
2 Correct 22 ms 9680 KB Output is correct
3 Correct 228 ms 23772 KB Output is correct
4 Correct 240 ms 24328 KB Output is correct
5 Correct 255 ms 25072 KB Output is correct
6 Correct 321 ms 27420 KB Output is correct
7 Correct 220 ms 24100 KB Output is correct
8 Correct 245 ms 24556 KB Output is correct
9 Correct 243 ms 24876 KB Output is correct
10 Correct 294 ms 27484 KB Output is correct
11 Correct 351 ms 27668 KB Output is correct
12 Correct 355 ms 27428 KB Output is correct
13 Correct 335 ms 26688 KB Output is correct
14 Correct 368 ms 26708 KB Output is correct
15 Correct 348 ms 26744 KB Output is correct
16 Correct 315 ms 26712 KB Output is correct
17 Correct 320 ms 26696 KB Output is correct
18 Correct 321 ms 27008 KB Output is correct
19 Correct 305 ms 27008 KB Output is correct
20 Correct 324 ms 27228 KB Output is correct
21 Correct 291 ms 27552 KB Output is correct
22 Correct 339 ms 27488 KB Output is correct
23 Correct 278 ms 27560 KB Output is correct
24 Correct 288 ms 27300 KB Output is correct
25 Correct 327 ms 27476 KB Output is correct
26 Correct 299 ms 27540 KB Output is correct
27 Correct 220 ms 23352 KB Output is correct
28 Correct 227 ms 23420 KB Output is correct
29 Correct 241 ms 23792 KB Output is correct
30 Correct 224 ms 23656 KB Output is correct
31 Correct 249 ms 23516 KB Output is correct
32 Correct 225 ms 23456 KB Output is correct
33 Correct 228 ms 23796 KB Output is correct
34 Correct 220 ms 23432 KB Output is correct
35 Correct 223 ms 23572 KB Output is correct
36 Correct 231 ms 23424 KB Output is correct
37 Correct 220 ms 23644 KB Output is correct
38 Correct 257 ms 23992 KB Output is correct
39 Correct 300 ms 27452 KB Output is correct
40 Correct 317 ms 27524 KB Output is correct
41 Correct 303 ms 27720 KB Output is correct
42 Correct 295 ms 27356 KB Output is correct