oj.uz

Submission #624155

# Submission time Handle Problem Language Result Execution time Memory
624155 2022-08-07T10:37:39 Z Ronin13 Highway Tolls (IOI18_highway) C++14
100 / 100
 516 ms 50512 KB 
#include "highway.h"
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int NMAX = 1e6 + 1;

vector <vector <int> > g(NMAX);

int D[NMAX][2];
vector <int> p(NMAX, -1);

int n;
ll a, b;
int d[NMAX][2];
ll sz1, sz2 = 0;

map<pii, bool> used1;
vector <bool> used(NMAX);

void bfs(int x, int y){
    queue <int> q;
    q.push(x);
    //cout << x << y;
    used1[{x, y}] = used1[{y, x}] = true;
    for(int i = 0; i < n; i++){
        D[i][0] = D[i][1] = 1e9;
        d[i][0] = d[i][1] = -1;
    }
    D[x][0] = 0;
    q.push(x);
    while(!q.empty()){
        int v = q.front();
       // cout << v << ' ';
        q.pop();
        for(int to : g[v]){
            if(D[to][0] > D[v][0] + 1){
                D[to][0] = D[v][0] + 1;
                q.push(to);
            }
        }
    }
    D[y][1] = 0;
    q.push(y);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(int to : g[v]){
            if(D[to][1] > D[v][1] + 1){
                D[to][1] = D[v][1] + 1;
                q.push(to);
            }
        }
    }
    q.push(x);
    int cnt = 1;
    d[x][0] = 0;
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(int to : g[v]){
            if(D[to][0] < D[to][1]){
                if(d[to][0] == -1) {d[to][0] = cnt++, sz1++, used1[{v, to}] = used1[{to, v}] = true, q.push(to); }
            }
        }
    }
    q.push(y);
    cnt = 1;
    d[y][1] = 0;
    while(!q.empty()){
        int v = q.front(); q.pop();
        for(int to : g[v]){
            if(D[to][1] <= D[to][0]){
                if(d[to][1] == -1) d[to][1] = cnt++, sz2++, used1[{v, to}] = used1[{to, v}] = true, q.push(to);
            }
        }
    }
}



void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    n = N;
    int m = U.size();
    for(int i = 0; i < m; i++){
        g[U[i]].pb(V[i]);
        g[V[i]].pb(U[i]);
    }
    ll a = A, b = B;
    vector <int> vec;
    vec.resize(m);
    const vector <int> v = vec;
    ll mn = ask(v);
    int l = -1, r = m;
    while(l + 1 < r){
        int mid = (l + r) / 2;
        vector <int> xx;
        for(int i = 0; i < m; i++){
            if(i <= mid) xx.pb(0);
            else xx.pb(1);
        }
        const vector <int> vv = xx;
        ll x = ask(vv);
        if(x == mn) r = mid;
        else l = mid;
    }
  //  cout << r << "\n";
    int x = U[r], y = V[r];
    bfs(x, y);
    for(int i = 0; i < m; i++){
        if(used1[{U[i], V[i]}]) used[i] = true;
    }

    l = -1, r = sz1 + 1;
    while(l + 1 < r){
        int mid = (l + r) / 2;
        vector <int> xx;
        for(int i = 0; i < m; i++){
            int u = U[i], v = V[i];
            if(!used[i]) xx.pb(1);
            else{
                if(d[u][0] <= mid && d[v][0] <= mid) xx.pb(0);
                else xx.pb(1);
            }
        }
        const vector <int> vv = xx;
        ll x = ask(vv);
        if(x == mn) r = mid;
        else l = mid;
    }
    int s;
    for(int i = 0; i < n; i++) if(d[i][0] == r) {s = i; break;}
    //cout << s << "\n";
    l = -1, r = sz2;
    while(l + 1 < r){
        int mid = (l + r) / 2;
        vector <int> xx;
        for(int i = 0; i < m; i++){
            int u = U[i], v = V[i];
            if(!used[i]) xx.pb(1);
            else{
                if(d[u][1] <= mid && d[v][1] <= mid) xx.pb(0);
                else xx.pb(1);
            }
        }
        const vector <int> vv = xx;
        ll x = ask(vv);
        if(x == mn) r = mid;
        else l = mid;
    }
    //cout << r;
    int t;
    for(int i = 0; i < n; i++) if(d[i][1] == r) {t = i; break;}
    answer(s, t);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:96:8: warning: unused variable 'a' [-Wunused-variable]
   96 |     ll a = A, b = B;
      |        ^
highway.cpp:96:15: warning: unused variable 'b' [-Wunused-variable]
   96 |     ll a = A, b = B;
      |               ^
highway.cpp:161:11: warning: 'second' may be used uninitialized in this function [-Wmaybe-uninitialized]
  161 |     answer(s, t);
      |     ~~~~~~^~~~~~
highway.cpp:161:11: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27856 KB Output is correct
2 Correct 16 ms 27768 KB Output is correct
3 Correct 15 ms 27752 KB Output is correct
4 Correct 15 ms 27856 KB Output is correct
5 Correct 15 ms 27784 KB Output is correct
6 Correct 18 ms 27856 KB Output is correct
7 Correct 15 ms 27764 KB Output is correct
8 Correct 19 ms 27752 KB Output is correct
9 Correct 16 ms 27856 KB Output is correct
10 Correct 15 ms 27788 KB Output is correct
11 Correct 15 ms 27856 KB Output is correct
12 Correct 16 ms 27872 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27948 KB Output is correct
2 Correct 34 ms 29900 KB Output is correct
3 Correct 334 ms 46448 KB Output is correct
4 Correct 300 ms 46448 KB Output is correct
5 Correct 368 ms 46432 KB Output is correct
6 Correct 304 ms 46548 KB Output is correct
7 Correct 276 ms 46596 KB Output is correct
8 Correct 312 ms 46496 KB Output is correct
9 Correct 361 ms 46456 KB Output is correct
10 Correct 315 ms 46452 KB Output is correct
11 Correct 299 ms 46448 KB Output is correct
12 Correct 305 ms 46332 KB Output is correct
13 Correct 316 ms 46340 KB Output is correct
14 Correct 355 ms 46336 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 29904 KB Output is correct
2 Correct 47 ms 31956 KB Output is correct
3 Correct 58 ms 34124 KB Output is correct
4 Correct 244 ms 46384 KB Output is correct
5 Correct 170 ms 46448 KB Output is correct
6 Correct 194 ms 46376 KB Output is correct
7 Correct 163 ms 46380 KB Output is correct
8 Correct 181 ms 46424 KB Output is correct
9 Correct 159 ms 46324 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28012 KB Output is correct
2 Correct 36 ms 29832 KB Output is correct
3 Correct 264 ms 42488 KB Output is correct
4 Correct 281 ms 46444 KB Output is correct
5 Correct 281 ms 46468 KB Output is correct
6 Correct 310 ms 46484 KB Output is correct
7 Correct 242 ms 46464 KB Output is correct
8 Correct 282 ms 46416 KB Output is correct
9 Correct 290 ms 46516 KB Output is correct
10 Correct 310 ms 46448 KB Output is correct
11 Correct 331 ms 46448 KB Output is correct
12 Correct 310 ms 46488 KB Output is correct
13 Correct 325 ms 46352 KB Output is correct
14 Correct 308 ms 46396 KB Output is correct
15 Correct 306 ms 46660 KB Output is correct
16 Correct 276 ms 46484 KB Output is correct
17 Correct 289 ms 46348 KB Output is correct
18 Correct 329 ms 46352 KB Output is correct
19 Correct 273 ms 46472 KB Output is correct
20 Correct 293 ms 46392 KB Output is correct
21 Correct 245 ms 47068 KB Output is correct
22 Correct 230 ms 47076 KB Output is correct
23 Correct 263 ms 46992 KB Output is correct
24 Correct 268 ms 46884 KB Output is correct
25 Correct 313 ms 46568 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 30020 KB Output is correct
2 Correct 44 ms 30100 KB Output is correct
3 Correct 355 ms 47408 KB Output is correct
4 Correct 364 ms 48452 KB Output is correct
5 Correct 515 ms 50320 KB Output is correct
6 Correct 487 ms 50392 KB Output is correct
7 Correct 488 ms 50316 KB Output is correct
8 Correct 516 ms 50252 KB Output is correct
9 Correct 327 ms 44192 KB Output is correct
10 Correct 264 ms 44100 KB Output is correct
11 Correct 321 ms 45504 KB Output is correct
12 Correct 390 ms 48444 KB Output is correct
13 Correct 405 ms 49260 KB Output is correct
14 Correct 501 ms 50216 KB Output is correct
15 Correct 457 ms 50092 KB Output is correct
16 Correct 312 ms 45588 KB Output is correct
17 Correct 349 ms 46836 KB Output is correct
18 Correct 296 ms 47184 KB Output is correct
19 Correct 281 ms 46904 KB Output is correct
20 Correct 318 ms 47304 KB Output is correct
21 Correct 431 ms 50180 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 29896 KB Output is correct
2 Correct 38 ms 30024 KB Output is correct
3 Correct 305 ms 47604 KB Output is correct
4 Correct 394 ms 47848 KB Output is correct
5 Correct 366 ms 48392 KB Output is correct
6 Correct 451 ms 50452 KB Output is correct
7 Correct 337 ms 47492 KB Output is correct
8 Correct 341 ms 47864 KB Output is correct
9 Correct 303 ms 48320 KB Output is correct
10 Correct 474 ms 50356 KB Output is correct
11 Correct 438 ms 50512 KB Output is correct
12 Correct 382 ms 50316 KB Output is correct
13 Correct 279 ms 45540 KB Output is correct
14 Correct 286 ms 44064 KB Output is correct
15 Correct 314 ms 45356 KB Output is correct
16 Correct 303 ms 44216 KB Output is correct
17 Correct 280 ms 45360 KB Output is correct
18 Correct 266 ms 44092 KB Output is correct
19 Correct 405 ms 48320 KB Output is correct
20 Correct 402 ms 49392 KB Output is correct
21 Correct 476 ms 50160 KB Output is correct
22 Correct 422 ms 50052 KB Output is correct
23 Correct 427 ms 50268 KB Output is correct
24 Correct 379 ms 50188 KB Output is correct
25 Correct 432 ms 50152 KB Output is correct
26 Correct 474 ms 50240 KB Output is correct
27 Correct 263 ms 47196 KB Output is correct
28 Correct 295 ms 47172 KB Output is correct
29 Correct 290 ms 47368 KB Output is correct
30 Correct 288 ms 47240 KB Output is correct
31 Correct 282 ms 47016 KB Output is correct
32 Correct 248 ms 46828 KB Output is correct
33 Correct 264 ms 47376 KB Output is correct
34 Correct 296 ms 47244 KB Output is correct
35 Correct 299 ms 47148 KB Output is correct
36 Correct 322 ms 47148 KB Output is correct
37 Correct 260 ms 47348 KB Output is correct
38 Correct 325 ms 47276 KB Output is correct
39 Correct 437 ms 50248 KB Output is correct
40 Correct 438 ms 50164 KB Output is correct
41 Correct 417 ms 50296 KB Output is correct
42 Correct 435 ms 50220 KB Output is correct