oj.uz

Submission #358446

# Submission time Handle Problem Language Result Execution time Memory
358446 2021-01-25T14:07:28 Z talant117408 Highway Tolls (IOI18_highway) C++17
90 / 100
 298 ms 10964 KB 
#include "highway.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;

vector <vector <pii>> g;
int n, m;
ll len;

void find_pair(int N, vector <int> U, vector<int> V, int light, int heavy){
    n = N; m = sz(U);
    g.resize(n);
    for(int i = 0; i < m; i++){
        g[U[i]].pb(mp(V[i], i));
        g[V[i]].pb(mp(U[i], i));
    }
    
    vector <ll> dist(n);
    vector <int> q(m), edges;
    queue <int> K;
    
    len = ask(q)/light;
    for(auto &to : dist) to = 1e18;
    for(auto &to : q) to = 1;
    
    int l = 0, r = m-1;
    int s, t;
    int mn = 2e9;
    
    while(l <= r){
        int mid = (l+r) >> 1;
        for(int i = 0; i <= mid; i++) q[i] = 0;
        auto ans = ask(q);
        for(int i = 0; i <= mid; i++) q[i] = 1;
        if(ans%light == 0 && ans/light == len){
            mn = min(mn, mid);
            r = mid-1;
        }
        else{
            l = mid+1;
        }
    }
    dist[V[mn]] = 0;
    K.push(V[mn]);
    while(!K.empty()){
        auto v = K.front(); K.pop();
        for(auto to : g[v]){
            if(dist[to.first] > dist[v]+1){
                dist[to.first] = dist[v]+1;
                K.push(to.first);
                edges.pb(to.second);
            }
        }
    }
    for(auto &to : q) to = 1;
    l = 0; r = sz(edges)-1; mn = 2e9;
    while(l <= r){
        int mid = (l+r) >> 1;
        for(int i = 0; i <= mid; i++) q[edges[i]] = 0;
        auto ans = ask(q);
        for(int i = 0; i <= mid; i++) q[edges[i]] = 1;
        if(ans%light == 0 && ans/light == len){
            mn = min(mn, mid);
            r = mid-1;
        }
        else{
            l = mid+1;
        }
    }
    
    auto rebro = edges[mn];
    if(dist[U[rebro]] > dist[V[rebro]]){
        s = U[rebro];
    }
    else{
        s = V[rebro];
    }
    
    edges.clear();
    for(auto &to : dist) to = 1e18;
    dist[s] = 0;
    K.push(s);
    while(!K.empty()){
        auto v = K.front(); K.pop();
        for(auto to : g[v]){
            if(dist[to.first] > dist[v]+1){
                dist[to.first] = dist[v]+1;
                K.push(to.first);
                edges.pb(to.second);
            }
        }
    }
    
    for(auto &to : q) to = 1;
    
    l = 0; r = sz(edges)-1;
    mn = 2e9;
    while(l <= r){
        int mid = (l+r) >> 1;
        for(int i = 0; i <= mid; i++) q[edges[i]] = 0;
        auto ans = ask(q);
        for(int i = 0; i <= mid; i++) q[edges[i]] = 1;
        if(ans%light == 0 && ans/light == len){
            mn = min(mn, mid);
            r = mid-1;
        }
        else{
            l = mid+1;
        }
    }
    
    rebro = edges[mn];
    if(dist[U[rebro]] > dist[V[rebro]]){
        t = U[rebro];
    }
    else{
        t = V[rebro];
    }
    
    answer(s, t);
}
/*
4 3
7 13
0 3
0 1
1 2
2 3



15 14
7 13
3 12
0 1
1 3
1 4
3 8
3 9
4 10
4 11
10 13
11 14
0 2
2 5
2 6
2 7
7 12



15 16
7 13
3 12
0 1
1 3
1 4
3 8
3 9
4 10
4 11
10 13
11 14
0 2
2 5
2 6
2 7
7 12
3 10
3 4

7 9
1 2
0 1

0 3
1 2
0 4
0 5
5 6
0 2
6 1
3 1
4 1
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 15 ms 1260 KB Output is correct
3 Correct 169 ms 8960 KB Output is correct
4 Correct 172 ms 8860 KB Output is correct
5 Correct 217 ms 8968 KB Output is correct
6 Correct 216 ms 8956 KB Output is correct
7 Correct 163 ms 8968 KB Output is correct
8 Correct 147 ms 8968 KB Output is correct
9 Correct 163 ms 9076 KB Output is correct
10 Correct 216 ms 8956 KB Output is correct
11 Correct 161 ms 8532 KB Output is correct
12 Correct 171 ms 8404 KB Output is correct
13 Correct 219 ms 8404 KB Output is correct
14 Correct 168 ms 8400 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1280 KB Output is correct
2 Correct 33 ms 2228 KB Output is correct
3 Correct 36 ms 3104 KB Output is correct
4 Correct 116 ms 8420 KB Output is correct
5 Correct 122 ms 8484 KB Output is correct
6 Correct 153 ms 8476 KB Output is correct
7 Correct 121 ms 8412 KB Output is correct
8 Correct 132 ms 8564 KB Output is correct
9 Correct 128 ms 8352 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 19 ms 1260 KB Output is correct
3 Correct 149 ms 7168 KB Output is correct
4 Correct 189 ms 8952 KB Output is correct
5 Correct 163 ms 8956 KB Output is correct
6 Correct 194 ms 8956 KB Output is correct
7 Correct 146 ms 8984 KB Output is correct
8 Correct 142 ms 8952 KB Output is correct
9 Correct 210 ms 9080 KB Output is correct
10 Correct 199 ms 9064 KB Output is correct
11 Correct 222 ms 8400 KB Output is correct
12 Correct 214 ms 8400 KB Output is correct
13 Correct 184 ms 8404 KB Output is correct
14 Correct 183 ms 8528 KB Output is correct
15 Correct 169 ms 8968 KB Output is correct
16 Correct 144 ms 9016 KB Output is correct
17 Correct 182 ms 8408 KB Output is correct
18 Correct 172 ms 8408 KB Output is correct
19 Correct 167 ms 9064 KB Output is correct
20 Correct 148 ms 8460 KB Output is correct
21 Correct 126 ms 9380 KB Output is correct
22 Correct 181 ms 9404 KB Output is correct
23 Correct 181 ms 9472 KB Output is correct
24 Correct 151 ms 9288 KB Output is correct
25 Correct 164 ms 8532 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1392 KB Output is correct
2 Correct 20 ms 1388 KB Output is correct
3 Correct 227 ms 9492 KB Output is correct
4 Correct 257 ms 9808 KB Output is correct
5 Correct 268 ms 10676 KB Output is correct
6 Correct 236 ms 10920 KB Output is correct
7 Correct 287 ms 10764 KB Output is correct
8 Correct 225 ms 10964 KB Output is correct
9 Correct 171 ms 7064 KB Output is correct
10 Correct 184 ms 7392 KB Output is correct
11 Correct 194 ms 8264 KB Output is correct
12 Correct 204 ms 9932 KB Output is correct
13 Correct 246 ms 10384 KB Output is correct
14 Correct 271 ms 10760 KB Output is correct
15 Correct 274 ms 10744 KB Output is correct
16 Correct 230 ms 8328 KB Output is correct
17 Correct 175 ms 9372 KB Output is correct
18 Correct 191 ms 9468 KB Output is correct
19 Correct 196 ms 9412 KB Output is correct
20 Correct 170 ms 9504 KB Output is correct
21 Correct 222 ms 10688 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1388 KB Output is correct
2 Correct 20 ms 1496 KB Output is correct
3 Correct 165 ms 9360 KB Output is correct
4 Partially correct 197 ms 9536 KB Output is partially correct
5 Partially correct 202 ms 9724 KB Output is partially correct
6 Partially correct 261 ms 10720 KB Output is partially correct
7 Correct 171 ms 9444 KB Output is correct
8 Partially correct 229 ms 9512 KB Output is partially correct
9 Partially correct 251 ms 9676 KB Output is partially correct
10 Partially correct 268 ms 10780 KB Output is partially correct
11 Partially correct 235 ms 10764 KB Output is partially correct
12 Partially correct 222 ms 10748 KB Output is partially correct
13 Correct 193 ms 8180 KB Output is correct
14 Correct 175 ms 7484 KB Output is correct
15 Correct 174 ms 8140 KB Output is correct
16 Correct 178 ms 7468 KB Output is correct
17 Correct 175 ms 8136 KB Output is correct
18 Correct 176 ms 7620 KB Output is correct
19 Partially correct 266 ms 9880 KB Output is partially correct
20 Partially correct 259 ms 10316 KB Output is partially correct
21 Partially correct 298 ms 10728 KB Output is partially correct
22 Partially correct 262 ms 10776 KB Output is partially correct
23 Partially correct 274 ms 10892 KB Output is partially correct
24 Partially correct 238 ms 10864 KB Output is partially correct
25 Partially correct 223 ms 10788 KB Output is partially correct
26 Partially correct 287 ms 10728 KB Output is partially correct
27 Correct 201 ms 9560 KB Output is correct
28 Correct 193 ms 9416 KB Output is correct
29 Partially correct 173 ms 9572 KB Output is partially correct
30 Correct 177 ms 9636 KB Output is correct
31 Partially correct 198 ms 9420 KB Output is partially correct
32 Partially correct 200 ms 9388 KB Output is partially correct
33 Partially correct 162 ms 9720 KB Output is partially correct
34 Partially correct 158 ms 9528 KB Output is partially correct
35 Correct 142 ms 9364 KB Output is correct
36 Correct 169 ms 9352 KB Output is correct
37 Correct 165 ms 9584 KB Output is correct
38 Partially correct 162 ms 9420 KB Output is partially correct
39 Correct 271 ms 10700 KB Output is correct
40 Partially correct 278 ms 10700 KB Output is partially correct
41 Partially correct 250 ms 10728 KB Output is partially correct
42 Partially correct 223 ms 10732 KB Output is partially correct