oj.uz

Submission #964342

# Submission time Handle Problem Language Result Execution time Memory
964342 2024-04-16T16:51:30 Z steveonalex Highway Tolls (IOI18_highway) C++17
100 / 100
 171 ms 18976 KB 
#include <bits/stdc++.h>
#include "highway.h"
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
 
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
        for(auto i: a) out << i << separator;
        out << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const int N = 1e5 + 69;
int n, m;
vector<pair<int,int>> graph[N];
vector<pair<int, int>> DAG[N];

void dfs(int u, vector<int> &topo){
    for(pair<int, int> v: DAG[u]){
        dfs(v.first, topo);
        topo.push_back(v.second);
    }
}

// struct P{
//     ll i, w;
//     P(){}
//     P(ll _i, ll _w){i = _i, w = _w;}
// };

// struct compare{
//     bool operator () (P a, P b) {return a.w > b.w;}
// };

// namespace Grader{
//     int n, m;
//     int s, t;
//     int x, y;
//     vector<int> U, V;
//     int A, B;
//     int o_cnt = 0;

//     ll ask(vector<int> w){
//         o_cnt++;
//         vector<vector<P>> graph(n);
//         for(int i = 0; i<w.size(); ++i){
//             int u = U[i], v = V[i];
//             int cur_w = A;
//             if (w[i]) cur_w = B;
//             graph[u].push_back(P(v, cur_w));
//             graph[v].push_back(P(u, cur_w));
//         }
//         vector<ll> dis(n+1, 1e18);
//         dis[s] = 0;
//         priority_queue<P, vector<P>, compare> pq; 
//         pq.push(P(s, 0));
//         while(pq.size()){
//             P u= pq.top(); pq.pop();
//             for(P v: graph[u.i]) if (minimize(dis[v.i], dis[u.i] + v.w)) 
//                 pq.push(P(v.i, dis[v.i]));
//         }
//         return dis[t];
//     }

//     void answer(int _x, int _y){
//         x = _x, y = _y;
//     }

    void find_pair(int _n, vector<int> U, vector<int> V, int A, int B) {
        n = _n, m = U.size();
        for(int i = 0; i<n; ++i) {
            graph[i].clear();
            DAG[i].clear();
        }

        ll initial = ask(vector<int>(m));
        int l = 0, r = m - 1;
        while(l < r){
            int mid = (l + r) >> 1;
            vector<int> w(m);
            for(int i = 0; i<=mid; ++i) w[i] = 1;
            if (ask(w) > initial) r = mid;
            else l = mid + 1;
        }

        if (l == m - 1) {
            answer(U[l], V[l]);
            return;
        }

        for(int i = l + 1; i<m; ++i){
            int u = U[i], v = V[i];
            graph[u].push_back({v, i});
            graph[v].push_back({u, i});
        }

        int u = U[l], v = V[l];
        vector<int> dis(n, 1e9);
        dis[u] = dis[v] = 0;
        deque<int> q; q.push_back(u); q.push_back(v);
        while(q.size()){
            int u= q.front(); q.pop_front();
            if (dis[u] == initial / A - 1) continue;
            for(pair<int, int> v: graph[u]) if (minimize(dis[v.first], dis[u] + 1)){
                q.push_back(v.first);
                DAG[u].push_back(v);
            }
        }

        vector<int> S1, S2;
        dfs(u, S1); dfs(v, S2);

        vector<int> S = S1;
        for(int i: S2) S.push_back(i);
        remove_dup(S);

        vector<int> _w(m);
        for(int i = 0; i<m; ++i){
            if (!binary_search(ALL(S), i)) _w[i] = 1;
        }
        _w[l] = 0;
        
        int x, y;
        l = 0, r = S1.size();
        while(l < r){
            int mid = (l + r) >> 1;
            vector<int> w = _w;
            for(int i = 0; i<=mid; ++i) w[S1[i]] = 1;
            if (ask(w) > initial) r = mid;
            else l = mid + 1;
        }
        if (l == S1.size()) x = u;
        else{
            if (dis[U[S1[l]]] > dis[V[S1[l]]]) x = U[S1[l]];
            else x = V[S1[l]];
        }

        l = 0, r = S2.size();
        while(l < r){
            int mid = (l + r) >> 1;
            vector<int> w = _w;
            for(int i = 0; i<=mid; ++i) w[S2[i]] = 1;
            if (ask(w) > initial) r = mid;
            else l = mid + 1;
        }
        if (l == S2.size()) y = v;
        else{
            if (dis[U[S2[l]]] > dis[V[S2[l]]]) y = U[S2[l]];
            else y = V[S2[l]];
        }
        answer(x, y);
    }

//     pair<bool, int> solve(int _n, int _m){
//         n = _n, m = _m;
//         U.clear(); V.clear();
//         x = y = -1;
//         o_cnt = 0;
//         for(int i= 1; i<n; ++i){
//             U.push_back(rngesus(0, i-1));
//             V.push_back(i);
//             if (rngesus(0, 1)) swap(U.back(), V.back());
//         }
//         for(int i = n; i<=m; ++i){
//             int u = rngesus(0, n-1);
//             int v = u;
//             while(u == v) v = rngesus(0, n-1);
//             U.push_back(u);
//             V.push_back(v);
//         }

//         s = rngesus(0, n-1);
//         t = s;
//         while(t == s) t = rngesus(0, n-1);

//         A = 1, B = 2;

//         find_pair(n, U, V, A, B);

//         if (x > y) swap(x, y);
//         if (s > t) swap(s, t);
//         return make_pair(make_pair(x, y) == make_pair(s, t), o_cnt);
//     }
// }


// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     for(int iteration = 1; iteration <= 100; ++iteration){
//         pair<bool, int> verdict = Grader::solve(100, rngesus(99, 111));
//         if (verdict.first) cout << "AC\n";
//         else cout << "WA\n";

//         cout << "Operation count: " << verdict.second << "\n";

//         if (verdict.first == false) break;
//     }

//     return 0;
// }

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:166:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |         if (l == S1.size()) x = u;
      |             ~~^~~~~~~~~~~~
highway.cpp:180:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |         if (l == S2.size()) y = v;
      |             ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5136 KB Output is correct
2 Correct 2 ms 5152 KB Output is correct
3 Correct 1 ms 5144 KB Output is correct
4 Correct 1 ms 5140 KB Output is correct
5 Correct 1 ms 5140 KB Output is correct
6 Correct 1 ms 5396 KB Output is correct
7 Correct 1 ms 5144 KB Output is correct
8 Correct 2 ms 5208 KB Output is correct
9 Correct 1 ms 5144 KB Output is correct
10 Correct 2 ms 5144 KB Output is correct
11 Correct 2 ms 5140 KB Output is correct
12 Correct 1 ms 5140 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5164 KB Output is correct
2 Correct 15 ms 6032 KB Output is correct
3 Correct 98 ms 12932 KB Output is correct
4 Correct 91 ms 13204 KB Output is correct
5 Correct 98 ms 13516 KB Output is correct
6 Correct 103 ms 12280 KB Output is correct
7 Correct 92 ms 12212 KB Output is correct
8 Correct 108 ms 12592 KB Output is correct
9 Correct 75 ms 10944 KB Output is correct
10 Correct 103 ms 13296 KB Output is correct
11 Correct 87 ms 11272 KB Output is correct
12 Correct 102 ms 13656 KB Output is correct
13 Correct 87 ms 12748 KB Output is correct
14 Correct 126 ms 13092 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5692 KB Output is correct
2 Correct 24 ms 6564 KB Output is correct
3 Correct 23 ms 6052 KB Output is correct
4 Correct 93 ms 11428 KB Output is correct
5 Correct 91 ms 9828 KB Output is correct
6 Correct 82 ms 16108 KB Output is correct
7 Correct 80 ms 7996 KB Output is correct
8 Correct 76 ms 13264 KB Output is correct
9 Correct 60 ms 8532 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5168 KB Output is correct
2 Correct 12 ms 5916 KB Output is correct
3 Correct 60 ms 9676 KB Output is correct
4 Correct 125 ms 11860 KB Output is correct
5 Correct 69 ms 10712 KB Output is correct
6 Correct 79 ms 10820 KB Output is correct
7 Correct 81 ms 10976 KB Output is correct
8 Correct 93 ms 10644 KB Output is correct
9 Correct 99 ms 13240 KB Output is correct
10 Correct 114 ms 12952 KB Output is correct
11 Correct 122 ms 13632 KB Output is correct
12 Correct 99 ms 15212 KB Output is correct
13 Correct 94 ms 13048 KB Output is correct
14 Correct 81 ms 11996 KB Output is correct
15 Correct 107 ms 10788 KB Output is correct
16 Correct 74 ms 9824 KB Output is correct
17 Correct 106 ms 13924 KB Output is correct
18 Correct 111 ms 13696 KB Output is correct
19 Correct 61 ms 10476 KB Output is correct
20 Correct 89 ms 10864 KB Output is correct
21 Correct 71 ms 11184 KB Output is correct
22 Correct 67 ms 9056 KB Output is correct
23 Correct 112 ms 13480 KB Output is correct
24 Correct 111 ms 13500 KB Output is correct
25 Correct 99 ms 18976 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6092 KB Output is correct
2 Correct 15 ms 5988 KB Output is correct
3 Correct 119 ms 14320 KB Output is correct
4 Correct 106 ms 12736 KB Output is correct
5 Correct 145 ms 12516 KB Output is correct
6 Correct 162 ms 16000 KB Output is correct
7 Correct 115 ms 13492 KB Output is correct
8 Correct 106 ms 12380 KB Output is correct
9 Correct 117 ms 8652 KB Output is correct
10 Correct 95 ms 8956 KB Output is correct
11 Correct 96 ms 10620 KB Output is correct
12 Correct 124 ms 13848 KB Output is correct
13 Correct 165 ms 14992 KB Output is correct
14 Correct 141 ms 15280 KB Output is correct
15 Correct 166 ms 14488 KB Output is correct
16 Correct 123 ms 12432 KB Output is correct
17 Correct 87 ms 12596 KB Output is correct
18 Correct 97 ms 10800 KB Output is correct
19 Correct 94 ms 12708 KB Output is correct
20 Correct 99 ms 12244 KB Output is correct
21 Correct 105 ms 13352 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6268 KB Output is correct
2 Correct 14 ms 6128 KB Output is correct
3 Correct 136 ms 12924 KB Output is correct
4 Correct 122 ms 13640 KB Output is correct
5 Correct 131 ms 14300 KB Output is correct
6 Correct 112 ms 13376 KB Output is correct
7 Correct 126 ms 12528 KB Output is correct
8 Correct 141 ms 13072 KB Output is correct
9 Correct 87 ms 12044 KB Output is correct
10 Correct 130 ms 13152 KB Output is correct
11 Correct 130 ms 14572 KB Output is correct
12 Correct 123 ms 13156 KB Output is correct
13 Correct 101 ms 8380 KB Output is correct
14 Correct 109 ms 8344 KB Output is correct
15 Correct 135 ms 11004 KB Output is correct
16 Correct 100 ms 8984 KB Output is correct
17 Correct 131 ms 10952 KB Output is correct
18 Correct 88 ms 10544 KB Output is correct
19 Correct 142 ms 13364 KB Output is correct
20 Correct 137 ms 13080 KB Output is correct
21 Correct 154 ms 14824 KB Output is correct
22 Correct 127 ms 13600 KB Output is correct
23 Correct 153 ms 15724 KB Output is correct
24 Correct 163 ms 15004 KB Output is correct
25 Correct 132 ms 12792 KB Output is correct
26 Correct 170 ms 13948 KB Output is correct
27 Correct 82 ms 11788 KB Output is correct
28 Correct 84 ms 12216 KB Output is correct
29 Correct 86 ms 13460 KB Output is correct
30 Correct 79 ms 12992 KB Output is correct
31 Correct 91 ms 13168 KB Output is correct
32 Correct 82 ms 12612 KB Output is correct
33 Correct 107 ms 13716 KB Output is correct
34 Correct 83 ms 12544 KB Output is correct
35 Correct 108 ms 12764 KB Output is correct
36 Correct 105 ms 13180 KB Output is correct
37 Correct 107 ms 13064 KB Output is correct
38 Correct 99 ms 12940 KB Output is correct
39 Correct 119 ms 13624 KB Output is correct
40 Correct 171 ms 13844 KB Output is correct
41 Correct 160 ms 16264 KB Output is correct
42 Correct 129 ms 13256 KB Output is correct