oj.uz

Submission #968356

# Submission time Handle Problem Language Result Execution time Memory
968356 2024-04-23T10:48:57 Z GrindMachine Highway Tolls (IOI18_highway) C++17
23 / 100
 183 ms 20604 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
    int 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 2648 KB Output is correct
6 Correct 1 ms 2648 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 2648 KB Output is correct
10 Correct 2 ms 2648 KB Output is correct
11 Correct 2 ms 2648 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2852 KB Output is correct
2 Correct 16 ms 3600 KB Output is correct
3 Correct 120 ms 10172 KB Output is correct
4 Correct 117 ms 9924 KB Output is correct
5 Correct 118 ms 10392 KB Output is correct
6 Correct 136 ms 10164 KB Output is correct
7 Correct 99 ms 10388 KB Output is correct
8 Correct 88 ms 10160 KB Output is correct
9 Correct 102 ms 9960 KB Output is correct
10 Correct 133 ms 10404 KB Output is correct
11 Correct 85 ms 9188 KB Output is correct
12 Correct 107 ms 10096 KB Output is correct
13 Correct 88 ms 9628 KB Output is correct
14 Runtime error 84 ms 17876 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3544 KB Output is correct
2 Correct 24 ms 4196 KB Output is correct
3 Correct 41 ms 4808 KB Output is correct
4 Correct 104 ms 9184 KB Output is correct
5 Correct 81 ms 8940 KB Output is correct
6 Correct 65 ms 8932 KB Output is correct
7 Correct 109 ms 9404 KB Output is correct
8 Correct 63 ms 9180 KB Output is correct
9 Runtime error 86 ms 17640 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2852 KB Output is correct
2 Correct 10 ms 3740 KB Output is correct
3 Correct 66 ms 8892 KB Output is correct
4 Correct 116 ms 10156 KB Output is correct
5 Correct 78 ms 10136 KB Output is correct
6 Correct 128 ms 10140 KB Output is correct
7 Correct 91 ms 10172 KB Output is correct
8 Correct 84 ms 10400 KB Output is correct
9 Runtime error 94 ms 19656 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3532 KB Output is correct
2 Correct 13 ms 3576 KB Output is correct
3 Correct 121 ms 9880 KB Output is correct
4 Correct 132 ms 10368 KB Output is correct
5 Correct 132 ms 12140 KB Output is correct
6 Correct 158 ms 12792 KB Output is correct
7 Correct 143 ms 12136 KB Output is correct
8 Correct 159 ms 12568 KB Output is correct
9 Correct 106 ms 10152 KB Output is correct
10 Correct 135 ms 10344 KB Output is correct
11 Correct 132 ms 11272 KB Output is correct
12 Correct 126 ms 11836 KB Output is correct
13 Correct 125 ms 12216 KB Output is correct
14 Correct 135 ms 12152 KB Output is correct
15 Correct 183 ms 12144 KB Output is correct
16 Correct 162 ms 11440 KB Output is correct
17 Correct 98 ms 10516 KB Output is correct
18 Correct 86 ms 10488 KB Output is correct
19 Correct 79 ms 10220 KB Output is correct
20 Correct 90 ms 10420 KB Output is correct
21 Correct 129 ms 12204 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3536 KB Output is correct
2 Correct 13 ms 3540 KB Output is correct
3 Partially correct 94 ms 10316 KB Output is partially correct
4 Correct 104 ms 11084 KB Output is correct
5 Partially correct 122 ms 10584 KB Output is partially correct
6 Partially correct 151 ms 12332 KB Output is partially correct
7 Correct 96 ms 10160 KB Output is correct
8 Partially correct 92 ms 10364 KB Output is partially correct
9 Partially correct 118 ms 10376 KB Output is partially correct
10 Partially correct 145 ms 12152 KB Output is partially correct
11 Partially correct 153 ms 12376 KB Output is partially correct
12 Correct 169 ms 12124 KB Output is correct
13 Correct 173 ms 10816 KB Output is correct
14 Correct 105 ms 10584 KB Output is correct
15 Correct 133 ms 11044 KB Output is correct
16 Correct 162 ms 10572 KB Output is correct
17 Correct 132 ms 11048 KB Output is correct
18 Correct 123 ms 10572 KB Output is correct
19 Correct 174 ms 12288 KB Output is correct
20 Correct 122 ms 11812 KB Output is correct
21 Partially correct 176 ms 12344 KB Output is partially correct
22 Partially correct 138 ms 12344 KB Output is partially correct
23 Correct 141 ms 12120 KB Output is correct
24 Partially correct 180 ms 12788 KB Output is partially correct
25 Partially correct 131 ms 12272 KB Output is partially correct
26 Partially correct 141 ms 12340 KB Output is partially correct
27 Correct 128 ms 10208 KB Output is correct
28 Correct 92 ms 10348 KB Output is correct
29 Correct 95 ms 10504 KB Output is correct
30 Runtime error 84 ms 20604 KB Execution killed with signal 6
31 Halted 0 ms 0 KB -