oj.uz

Submission #1060602

# Submission time Handle Problem Language Result Execution time Memory
1060602 2024-08-15T18:20:06 Z ewirlan Highway Tolls (IOI18_highway) C++17
90 / 100
 165 ms 10480 KB 
//
#ifndef __SIZEOF_INT128__
  #define __SIZEOF_INT128__
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "highway.h"
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template <typename T> using oset =  tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define rep(i, p, k) for(int i(p); i < (k); ++i)
#define per(i, p, k) for(int i(p); i > (k); --i)
#define sz(x) (int)(x).size()
#define sc static_cast
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef __int128_t lll;
//#define int ll
template <typename T = int> using par = std::pair <T, T>;
#define fi first
#define se second
#define test int _number_of_tests(in()); while(_number_of_tests--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb emplace_back
struct Timer {
    string name{""};
    time_point<high_resolution_clock> end, start{high_resolution_clock::now()};
    duration<float, std::milli> dur;
    Timer() = default;
    Timer(string nm): name(nm) {}
    ~Timer() {
        end = high_resolution_clock::now(); dur= end - start;
        cout << "@" << name << "> " << dur.count() << " ms" << '\n';
    }
};
template <typename T = int> inline T in()
{
    static T x;
    std::cin >> x;
    return x;
}
std::string yn(bool b)
{
    if(b) return "YES\n";
    else return "NO\n";
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par);
template <typename T> std::ostream& operator<< (std::ostream& out, const std::vector <T>& wek)
{
    for(const auto& i : wek)out << i << ' ';
    return out;
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par)
{
    out << '{'<<par.first<<", "<<par.second<<"}";
    return out;
}
#define show(x) cerr << #x << " = " << x << '\n';
constexpr int maxn = 90003;
vector <pair<int, int>> graf[maxn];
int odl[maxn];
void find_pair(int n, vector <int> ka, vector <int> kb, int a, int b)
{
    int m(sz(ka));
    rep(i, 0, m){
        graf[ka[i]].pb(kb[i], i);
        graf[kb[i]].pb(ka[i], i);
    }
    ll d(ask(vector<int>(m, 0))/a);
    auto pyt = [n,m](vector <bool> v){
        vector <int> w(m);
        rep(i, 0, n)if(v[i])for(auto [i, j]: graf[i])w[j] |= 1;
        return ask(w);
    };
    int p(0), k(n), s;
    vector <bool> v(n);
    while(k > p){
        s = (p+k)/2;
        rep(i, 0, n)v[i] = i >= s;
        if(pyt(v) == d*a)k = s;
        else p = s+1;
    }
    int r(p-1);
    vector <int> so;
    queue <int> kul; 
    bool je(0);
rp:
    rep(i, 0, n)odl[i] = 0;
    so = {r};
    kul.push(r);
    odl[r] = 1;
    while(kul.size()){
        auto t(kul.front()); kul.pop();
        for(auto [i, j]: graf[t])if(!odl[i]){
            kul.push(i);
            so.pb(i);
            odl[i] = odl[t]+1;
        }
    }
    if(je){
        vector <int> s;
        for(auto i: so)if(odl[i] == d+1)s.pb(i);
        so = s;
    }
    p = 0, k = sz(so);
    while(k > p){
        s = (p+k)/2;
        rep(i, 0, n)v[i] = 0;
        rep(i, 0, sz(so))v[so[i]] = i >= s;
        if(pyt(v) == d*a)k = s;
        else p = s+1;
    }
    if(!je){
        r = so[p-1];
        je = 1;
        goto rp;
    }
    answer(r, so[p-1]);
}

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 1 ms 2740 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 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 2648 KB Output is correct
2 Correct 11 ms 3380 KB Output is correct
3 Correct 107 ms 8560 KB Output is correct
4 Correct 103 ms 8540 KB Output is correct
5 Correct 109 ms 8548 KB Output is correct
6 Correct 105 ms 8548 KB Output is correct
7 Correct 106 ms 8552 KB Output is correct
8 Correct 98 ms 8556 KB Output is correct
9 Correct 97 ms 8580 KB Output is correct
10 Correct 95 ms 8552 KB Output is correct
11 Correct 93 ms 8156 KB Output is correct
12 Correct 95 ms 8008 KB Output is correct
13 Correct 94 ms 8004 KB Output is correct
14 Correct 83 ms 8312 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3160 KB Output is correct
2 Correct 15 ms 3824 KB Output is correct
3 Correct 24 ms 4628 KB Output is correct
4 Correct 67 ms 8000 KB Output is correct
5 Correct 69 ms 8020 KB Output is correct
6 Correct 70 ms 7880 KB Output is correct
7 Correct 71 ms 8016 KB Output is correct
8 Correct 84 ms 7816 KB Output is correct
9 Correct 73 ms 8256 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 11 ms 3384 KB Output is correct
3 Correct 69 ms 7232 KB Output is correct
4 Correct 95 ms 8680 KB Output is correct
5 Correct 99 ms 8540 KB Output is correct
6 Correct 91 ms 8784 KB Output is correct
7 Correct 96 ms 8568 KB Output is correct
8 Correct 100 ms 8556 KB Output is correct
9 Correct 103 ms 8556 KB Output is correct
10 Correct 127 ms 9028 KB Output is correct
11 Correct 91 ms 8000 KB Output is correct
12 Correct 102 ms 8000 KB Output is correct
13 Correct 99 ms 8000 KB Output is correct
14 Correct 91 ms 8000 KB Output is correct
15 Correct 101 ms 8564 KB Output is correct
16 Correct 89 ms 8552 KB Output is correct
17 Correct 97 ms 8008 KB Output is correct
18 Correct 96 ms 8172 KB Output is correct
19 Correct 99 ms 8796 KB Output is correct
20 Correct 78 ms 8012 KB Output is correct
21 Correct 92 ms 9400 KB Output is correct
22 Correct 91 ms 9368 KB Output is correct
23 Correct 86 ms 8728 KB Output is correct
24 Correct 90 ms 8644 KB Output is correct
25 Correct 100 ms 8308 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3496 KB Output is correct
2 Correct 14 ms 3416 KB Output is correct
3 Correct 122 ms 8860 KB Output is correct
4 Correct 135 ms 9280 KB Output is correct
5 Correct 146 ms 10232 KB Output is correct
6 Correct 157 ms 10240 KB Output is correct
7 Correct 140 ms 10232 KB Output is correct
8 Correct 144 ms 10228 KB Output is correct
9 Correct 103 ms 8520 KB Output is correct
10 Correct 114 ms 9036 KB Output is correct
11 Correct 118 ms 9364 KB Output is correct
12 Correct 146 ms 9956 KB Output is correct
13 Correct 165 ms 10088 KB Output is correct
14 Correct 140 ms 10300 KB Output is correct
15 Correct 127 ms 10240 KB Output is correct
16 Correct 127 ms 9884 KB Output is correct
17 Correct 108 ms 9328 KB Output is correct
18 Correct 111 ms 9604 KB Output is correct
19 Correct 114 ms 9240 KB Output is correct
20 Correct 103 ms 9304 KB Output is correct
21 Correct 124 ms 10228 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3416 KB Output is correct
2 Correct 11 ms 3416 KB Output is correct
3 Correct 145 ms 9284 KB Output is correct
4 Correct 140 ms 9052 KB Output is correct
5 Correct 129 ms 9604 KB Output is correct
6 Correct 147 ms 10236 KB Output is correct
7 Correct 118 ms 8900 KB Output is correct
8 Correct 121 ms 9048 KB Output is correct
9 Correct 145 ms 9428 KB Output is correct
10 Correct 152 ms 10256 KB Output is correct
11 Correct 156 ms 10252 KB Output is correct
12 Correct 159 ms 10224 KB Output is correct
13 Correct 122 ms 9352 KB Output is correct
14 Correct 104 ms 9024 KB Output is correct
15 Correct 105 ms 9368 KB Output is correct
16 Correct 116 ms 9164 KB Output is correct
17 Correct 139 ms 9368 KB Output is correct
18 Correct 119 ms 9092 KB Output is correct
19 Correct 142 ms 9964 KB Output is correct
20 Correct 145 ms 10204 KB Output is correct
21 Correct 150 ms 10260 KB Output is correct
22 Correct 156 ms 10352 KB Output is correct
23 Correct 162 ms 10436 KB Output is correct
24 Correct 165 ms 10240 KB Output is correct
25 Correct 146 ms 10236 KB Output is correct
26 Correct 142 ms 10256 KB Output is correct
27 Correct 108 ms 9300 KB Output is correct
28 Partially correct 95 ms 9128 KB Output is partially correct
29 Correct 103 ms 9456 KB Output is correct
30 Correct 100 ms 9384 KB Output is correct
31 Partially correct 108 ms 9156 KB Output is partially correct
32 Correct 96 ms 9440 KB Output is correct
33 Partially correct 102 ms 9464 KB Output is partially correct
34 Correct 99 ms 9292 KB Output is correct
35 Correct 97 ms 9284 KB Output is correct
36 Correct 99 ms 9092 KB Output is correct
37 Correct 113 ms 9852 KB Output is correct
38 Partially correct 101 ms 9256 KB Output is partially correct
39 Correct 131 ms 10480 KB Output is correct
40 Correct 135 ms 10244 KB Output is correct
41 Correct 126 ms 10196 KB Output is correct
42 Correct 124 ms 10216 KB Output is correct