oj.uz

Submission #968401

# Submission time Handle Problem Language Result Execution time Memory
968401 2024-04-23T11:34:37 Z GrindMachine Highway Tolls (IOI18_highway) C++17
51 / 100
 200 ms 13840 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

*/

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);

    // split into 2 sets: closer to x and closer to y
    auto bfs = [&](int r){
        queue<int> q;
        vector<int> dis(n,-1);
        q.push(r);
        dis[r] = 0;

        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;
            }
        }

        return dis;
    };

    auto [x,y] = edges[first];
    vector<int> node_type(n); // 0 = none, 1 = closer to x, 2 = closer to y
    auto dis1 = bfs(x);
    auto dis2 = bfs(y);
    rep(i,n){
        if(dis1[i] < dis2[i]) node_type[i] = 1;
        else if(dis2[i] < dis1[i]) node_type[i] = 2;
    }

    // bfs tree of x (ignore nodes with node_type[i] != 1)
    queue<int> q;
    vector<int> dis(n,-1);
    q.push(x);
    dis[x] = 0;
    vector<int> ord;

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

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

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

    while(lo <= hi){
        int mid = (lo+hi) >> 1;
        vector<int> w(m,1);
        rep(i,m){
            auto [u,v] = edges[i];
            if(node_type[u] != 1 or node_type[v] != 1){
                w[i] = 0;
            }
        }

        rep(i,mid){
            w[ord[i]] = 0;
        }

        auto res = ask(w);

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

    assert(first != -1);
    first--;

    int s = -1;

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

    // bfs tree of y (ignore nodes with node_type[i] != 2)
    fill(all(dis),-1);
    q.push(y);
    dis[y] = 0;
    ord.clear();

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

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

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

    while(lo <= hi){
        int mid = (lo+hi) >> 1;
        vector<int> w(m,1);
        rep(i,m){
            auto [u,v] = edges[i];
            if(node_type[u] != 2 or node_type[v] != 2){
                w[i] = 0;
            }
        }

        rep(i,mid){
            w[ord[i]] = 0;
        }

        auto res = ask(w);

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

    assert(first != -1);
    first--;

    int t = -1;
    
    if(first == -1){
        t = y;
    }
    else{
        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 2792 KB Output is correct
2 Correct 1 ms 3044 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 2 ms 2800 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2788 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2800 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2852 KB Output is correct
2 Correct 10 ms 3688 KB Output is correct
3 Correct 94 ms 11028 KB Output is correct
4 Correct 124 ms 11040 KB Output is correct
5 Correct 96 ms 10992 KB Output is correct
6 Correct 90 ms 11048 KB Output is correct
7 Correct 101 ms 11060 KB Output is correct
8 Correct 117 ms 10984 KB Output is correct
9 Correct 86 ms 11024 KB Output is correct
10 Correct 104 ms 10804 KB Output is correct
11 Correct 136 ms 10672 KB Output is correct
12 Correct 128 ms 10840 KB Output is correct
13 Correct 104 ms 10452 KB Output is correct
14 Correct 105 ms 10428 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3612 KB Output is correct
2 Correct 16 ms 4460 KB Output is correct
3 Correct 31 ms 5376 KB Output is correct
4 Correct 101 ms 10120 KB Output is correct
5 Correct 87 ms 9952 KB Output is correct
6 Correct 84 ms 10168 KB Output is correct
7 Correct 78 ms 9976 KB Output is correct
8 Correct 68 ms 10240 KB Output is correct
9 Correct 100 ms 9896 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2852 KB Output is correct
2 Correct 16 ms 3664 KB Output is correct
3 Correct 74 ms 9124 KB Output is correct
4 Correct 91 ms 10568 KB Output is correct
5 Correct 110 ms 10644 KB Output is correct
6 Correct 72 ms 10572 KB Output is correct
7 Correct 83 ms 10800 KB Output is correct
8 Correct 95 ms 11036 KB Output is correct
9 Correct 97 ms 11004 KB Output is correct
10 Correct 112 ms 11036 KB Output is correct
11 Correct 90 ms 10896 KB Output is correct
12 Correct 128 ms 10408 KB Output is correct
13 Correct 138 ms 10144 KB Output is correct
14 Correct 123 ms 10444 KB Output is correct
15 Correct 89 ms 10568 KB Output is correct
16 Correct 108 ms 10808 KB Output is correct
17 Correct 100 ms 10436 KB Output is correct
18 Correct 118 ms 10220 KB Output is correct
19 Correct 122 ms 10576 KB Output is correct
20 Correct 134 ms 10032 KB Output is correct
21 Correct 98 ms 11144 KB Output is correct
22 Correct 100 ms 11100 KB Output is correct
23 Correct 109 ms 11408 KB Output is correct
24 Correct 101 ms 11340 KB Output is correct
25 Correct 109 ms 10064 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3708 KB Output is correct
2 Correct 12 ms 3796 KB Output is correct
3 Correct 102 ms 11184 KB Output is correct
4 Correct 121 ms 12180 KB Output is correct
5 Correct 139 ms 13840 KB Output is correct
6 Correct 165 ms 13064 KB Output is correct
7 Correct 189 ms 13112 KB Output is correct
8 Incorrect 200 ms 13564 KB Output is incorrect: {s, t} is wrong.
9 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3712 KB Output is correct
2 Correct 11 ms 3768 KB Output is correct
3 Correct 160 ms 11528 KB Output is correct
4 Correct 159 ms 11952 KB Output is correct
5 Correct 139 ms 12204 KB Output is correct
6 Correct 156 ms 13008 KB Output is correct
7 Correct 121 ms 11240 KB Output is correct
8 Correct 142 ms 11616 KB Output is correct
9 Incorrect 169 ms 12120 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -