oj.uz

Submission #968362

# Submission time Handle Problem Language Result Execution time Memory
968362 2024-04-23T10:58:32 Z GrindMachine Highway Tolls (IOI18_highway) C++17
90 / 100
 184 ms 13032 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
http://www.algonotes.com/en/solutions-ioi2018/
edi

find an edge that lies on at least one sp from s to t
if edge is (u,v), then d(s,u)+d(u,t) = sp
can find s using bfs tree of u
once s found, t can also be found

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "highway.h"

vector<pii> adj[N];

void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
    int m = sz(U);
    vector<pii> edges;
    rep(i,m){
        int u = U[i], v = V[i];
        edges.pb({u,v});
        adj[u].pb({v,i}), adj[v].pb({u,i});
    }

    // find an edge that lies on at least one sp from s to t
    ll all_light = -1;

    {
        vector<int> w(m);
        all_light = ask(w);
    }

    int lo = 0, hi = m-1;
    int first = -1;

    while(lo <= hi){
        int mid = (lo+hi) >> 1;
        vector<int> w(m);
        rep(i,mid+1){
            w[i] = 1;
        }
        auto res = ask(w);

        if(res != all_light){
            first = mid;
            hi = mid-1;
        }
        else{
            lo = mid+1;
        }
    }
        
    assert(first != -1);

    // bfs tree of r
    int r = edges[first].ff;
    queue<int> q;
    vector<int> dis(n,-1);
    q.push(r);
    dis[r] = 0;
    vector<int> ord;

    while(!q.empty()){
        int u = q.front();
        q.pop();

        for(auto [v,id] : adj[u]){
            if(dis[v] != -1) conts;
            q.push(v);
            dis[v] = dis[u]+1;
            ord.pb(id);
        }
    }

    // find s
    lo = 0, hi = sz(ord)-1;
    first = -1;

    while(lo <= hi){
        int mid = (lo+hi) >> 1;
        vector<int> w(m,1);
        rep(i,mid+1){
            w[ord[i]] = 0;
        }

        auto res = ask(w);

        if(res == all_light){
            first = mid;
            hi = mid-1;
        }
        else{
            lo = mid+1;
        }
    }

    assert(first != -1);

    int s = -1;
    
    {
        auto [u,v] = edges[ord[first]];
        if(dis[u] > dis[v]) s = u;
        else s = v;
    }

    // bfs tree of s
    fill(all(dis),-1);
    q.push(s);
    dis[s] = 0;
    ord.clear();

    while(!q.empty()){
        int u = q.front();
        q.pop();

        for(auto [v,id] : adj[u]){
            if(dis[v] != -1) conts;
            q.push(v);
            dis[v] = dis[u]+1;
            ord.pb(id);
        }
    }

    // find t
    lo = 0, hi = sz(ord)-1;
    first = -1;

    while(lo <= hi){
        int mid = (lo+hi) >> 1;
        vector<int> w(m,1);
        rep(i,mid+1){
            w[ord[i]] = 0;
        }

        auto res = ask(w);

        if(res == all_light){
            first = mid;
            hi = mid-1;
        }
        else{
            lo = mid+1;
        }
    }

    assert(first != -1);

    int t = -1;
    
    {
        auto [u,v] = edges[ord[first]];
        if(dis[u] > dis[v]) t = u;
        else t = v;
    }

    answer(s,t);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2856 KB Output is correct
2 Correct 14 ms 3532 KB Output is correct
3 Correct 150 ms 10632 KB Output is correct
4 Correct 84 ms 10164 KB Output is correct
5 Correct 117 ms 10160 KB Output is correct
6 Correct 87 ms 9936 KB Output is correct
7 Correct 115 ms 10172 KB Output is correct
8 Correct 92 ms 10620 KB Output is correct
9 Correct 119 ms 9724 KB Output is correct
10 Correct 124 ms 10404 KB Output is correct
11 Correct 86 ms 8936 KB Output is correct
12 Correct 88 ms 9636 KB Output is correct
13 Correct 93 ms 9404 KB Output is correct
14 Correct 92 ms 9064 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3540 KB Output is correct
2 Correct 29 ms 4184 KB Output is correct
3 Correct 29 ms 5060 KB Output is correct
4 Correct 75 ms 9180 KB Output is correct
5 Correct 68 ms 8928 KB Output is correct
6 Correct 80 ms 9188 KB Output is correct
7 Correct 80 ms 9156 KB Output is correct
8 Correct 92 ms 8928 KB Output is correct
9 Correct 97 ms 8936 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2856 KB Output is correct
2 Correct 10 ms 3596 KB Output is correct
3 Correct 95 ms 8596 KB Output is correct
4 Correct 99 ms 10148 KB Output is correct
5 Correct 93 ms 10392 KB Output is correct
6 Correct 77 ms 10176 KB Output is correct
7 Correct 117 ms 9936 KB Output is correct
8 Correct 94 ms 9932 KB Output is correct
9 Correct 94 ms 10392 KB Output is correct
10 Correct 89 ms 10620 KB Output is correct
11 Correct 128 ms 9624 KB Output is correct
12 Correct 85 ms 8936 KB Output is correct
13 Correct 140 ms 9400 KB Output is correct
14 Correct 96 ms 9168 KB Output is correct
15 Correct 93 ms 10136 KB Output is correct
16 Correct 93 ms 10448 KB Output is correct
17 Correct 99 ms 9180 KB Output is correct
18 Correct 87 ms 9204 KB Output is correct
19 Correct 83 ms 9716 KB Output is correct
20 Correct 93 ms 9168 KB Output is correct
21 Correct 80 ms 10548 KB Output is correct
22 Correct 71 ms 10028 KB Output is correct
23 Correct 100 ms 10500 KB Output is correct
24 Correct 78 ms 9984 KB Output is correct
25 Correct 101 ms 9268 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3468 KB Output is correct
2 Correct 16 ms 3540 KB Output is correct
3 Correct 111 ms 10104 KB Output is correct
4 Correct 116 ms 10600 KB Output is correct
5 Correct 133 ms 12608 KB Output is correct
6 Correct 122 ms 12296 KB Output is correct
7 Correct 134 ms 12120 KB Output is correct
8 Correct 125 ms 12348 KB Output is correct
9 Correct 109 ms 10380 KB Output is correct
10 Correct 184 ms 11000 KB Output is correct
11 Correct 138 ms 10860 KB Output is correct
12 Correct 149 ms 11616 KB Output is correct
13 Correct 135 ms 11764 KB Output is correct
14 Correct 149 ms 12184 KB Output is correct
15 Correct 140 ms 12124 KB Output is correct
16 Correct 157 ms 11436 KB Output is correct
17 Correct 89 ms 10288 KB Output is correct
18 Correct 89 ms 11208 KB Output is correct
19 Correct 84 ms 10660 KB Output is correct
20 Correct 112 ms 10752 KB Output is correct
21 Correct 146 ms 12092 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3504 KB Output is correct
2 Correct 17 ms 3580 KB Output is correct
3 Partially correct 112 ms 9928 KB Output is partially correct
4 Correct 101 ms 10828 KB Output is correct
5 Partially correct 152 ms 10784 KB Output is partially correct
6 Partially correct 149 ms 12552 KB Output is partially correct
7 Correct 101 ms 9920 KB Output is correct
8 Partially correct 102 ms 10364 KB Output is partially correct
9 Partially correct 108 ms 10804 KB Output is partially correct
10 Partially correct 179 ms 12372 KB Output is partially correct
11 Partially correct 133 ms 12140 KB Output is partially correct
12 Correct 155 ms 12800 KB Output is correct
13 Correct 162 ms 10836 KB Output is correct
14 Correct 146 ms 11008 KB Output is correct
15 Correct 117 ms 10812 KB Output is correct
16 Correct 107 ms 10996 KB Output is correct
17 Correct 109 ms 11036 KB Output is correct
18 Correct 160 ms 11012 KB Output is correct
19 Correct 148 ms 12068 KB Output is correct
20 Correct 128 ms 11772 KB Output is correct
21 Partially correct 116 ms 12288 KB Output is partially correct
22 Partially correct 136 ms 12564 KB Output is partially correct
23 Correct 156 ms 12108 KB Output is correct
24 Partially correct 140 ms 12360 KB Output is partially correct
25 Partially correct 130 ms 13032 KB Output is partially correct
26 Partially correct 163 ms 13012 KB Output is partially correct
27 Correct 85 ms 11200 KB Output is correct
28 Correct 106 ms 10336 KB Output is correct
29 Correct 102 ms 10460 KB Output is correct
30 Partially correct 113 ms 10460 KB Output is partially correct
31 Correct 88 ms 10628 KB Output is correct
32 Partially correct 119 ms 10328 KB Output is partially correct
33 Partially correct 90 ms 10612 KB Output is partially correct
34 Partially correct 81 ms 11108 KB Output is partially correct
35 Correct 82 ms 10472 KB Output is correct
36 Partially correct 116 ms 10304 KB Output is partially correct
37 Partially correct 88 ms 10716 KB Output is partially correct
38 Correct 110 ms 10744 KB Output is correct
39 Correct 129 ms 12200 KB Output is correct
40 Partially correct 116 ms 12236 KB Output is partially correct
41 Partially correct 168 ms 12644 KB Output is partially correct
42 Partially correct 117 ms 12008 KB Output is partially correct