oj.uz

Submission #1060604

# Submission time Handle Problem Language Result Execution time Memory
1060604 2024-08-15T18:45:34 Z ewirlan Highway Tolls (IOI18_highway) C++17
51 / 100
 166 ms 11784 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];
bool xd[maxn];
void dfs(int w, bool x)
{
    odl[w] = 1;
    xd[w] = x;
    for(auto [i, j]: graf[w])if(!odl[i])dfs(i, !x);
}
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);
    }
    dfs(0, 0);
    vector <int> xdd[2];
    rep(i, 0, n)xdd[xd[i]].pb(i);
    vector vv = xdd[sz(xdd[1]) < sz(xdd[0])];
    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(sz(vv)), s;
    vector <bool> v(n);
    while(k > p){
        s = (p+k)/2;
        rep(i, 0, n)v[i] = 0;
        rep(i, 0, sz(vv))v[vv[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 2648 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 1 ms 2644 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 2736 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 2 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 2 ms 2904 KB Output is correct
2 Correct 14 ms 3640 KB Output is correct
3 Correct 98 ms 9172 KB Output is correct
4 Correct 103 ms 9336 KB Output is correct
5 Correct 115 ms 9192 KB Output is correct
6 Correct 93 ms 9172 KB Output is correct
7 Correct 110 ms 9172 KB Output is correct
8 Correct 97 ms 9188 KB Output is correct
9 Correct 101 ms 9704 KB Output is correct
10 Correct 100 ms 9180 KB Output is correct
11 Correct 91 ms 9040 KB Output is correct
12 Correct 102 ms 9216 KB Output is correct
13 Correct 98 ms 9080 KB Output is correct
14 Correct 94 ms 8932 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3672 KB Output is correct
2 Correct 16 ms 4676 KB Output is correct
3 Correct 23 ms 5352 KB Output is correct
4 Correct 82 ms 10236 KB Output is correct
5 Correct 87 ms 10332 KB Output is correct
6 Correct 73 ms 10320 KB Output is correct
7 Correct 77 ms 10240 KB Output is correct
8 Correct 75 ms 10344 KB Output is correct
9 Correct 86 ms 10580 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 13 ms 3568 KB Output is correct
3 Correct 89 ms 7860 KB Output is correct
4 Correct 109 ms 9168 KB Output is correct
5 Correct 97 ms 9180 KB Output is correct
6 Correct 104 ms 9332 KB Output is correct
7 Correct 87 ms 9176 KB Output is correct
8 Correct 102 ms 9168 KB Output is correct
9 Correct 106 ms 9188 KB Output is correct
10 Correct 113 ms 9476 KB Output is correct
11 Correct 100 ms 8880 KB Output is correct
12 Correct 85 ms 9168 KB Output is correct
13 Correct 106 ms 9112 KB Output is correct
14 Correct 106 ms 9220 KB Output is correct
15 Correct 117 ms 9300 KB Output is correct
16 Correct 112 ms 9176 KB Output is correct
17 Correct 93 ms 9152 KB Output is correct
18 Correct 107 ms 9020 KB Output is correct
19 Correct 121 ms 9180 KB Output is correct
20 Correct 91 ms 9384 KB Output is correct
21 Correct 85 ms 10216 KB Output is correct
22 Correct 82 ms 9756 KB Output is correct
23 Correct 104 ms 9196 KB Output is correct
24 Correct 90 ms 9376 KB Output is correct
25 Correct 103 ms 10128 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3600 KB Output is correct
2 Correct 12 ms 3776 KB Output is correct
3 Correct 116 ms 9828 KB Output is correct
4 Correct 139 ms 10396 KB Output is correct
5 Correct 163 ms 11600 KB Output is correct
6 Correct 157 ms 11784 KB Output is correct
7 Correct 145 ms 11600 KB Output is correct
8 Correct 166 ms 11608 KB Output is correct
9 Correct 91 ms 8768 KB Output is correct
10 Correct 90 ms 9272 KB Output is correct
11 Correct 111 ms 9704 KB Output is correct
12 Incorrect 155 ms 11220 KB Output is incorrect: {s, t} is wrong.
13 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 3672 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -