oj.uz

Submission #417392

# Submission time Handle Problem Language Result Execution time Memory
417392 2021-06-03T16:12:23 Z wiwiho Highway Tolls (IOI18_highway) C++14
100 / 100
 228 ms 18384 KB 
#include "highway.h"

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

int n, m;

#define query ask
//ll query(vector<int> qry){
//    ll tmp = ask(qry);
//    cerr << "query " << tmp << "  ";
//    printv(qry, cerr);
//    return tmp;
//}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    n = N;
    m = U.size();

    vector<vector<pii>> g(n);
    for(int i = 0; i < m; i++){
        int u = U[i], v = V[i];
        g[u].eb(mp(v, i));
        g[v].eb(mp(u, i));
    }

    vector<int> qry(m);
    ll dis = query(qry);

    int l = 0, r = m - 1;
    while(l < r){
        int mid = (l + r) / 2;
        fill(qry.begin() + l, qry.begin() + mid + 1, 1);
//        cerr << l << " " << r << " " << mid << "\n";
        if(query(qry) != dis){
            r = mid;
            fill(qry.begin() + l, qry.begin() + mid + 1, 0);
        }
        else l = mid + 1;
    }

    int e = l;
    int u = U[e], v = V[e];
//    cerr << e << " " << u << " " << v << "\n";

    auto getdis = [g](int s){
        vector<int> d(n, -1);
        vector<int> p(n, -1);
        queue<int> q;
        q.push(s);
        d[s] = 0;
        while(!q.empty()){
            int now = q.front();
            q.pop();
            for(pii i : g[now]){
                if(d[i.F] != -1) continue;
                p[i.F] = i.S;
                d[i.F] = d[now] + 1;
                q.push(i.F);
            }
        }
        return mp(d, p);
    };

    vector<int> du, pu, dv, pv;
    tie(du, pu) = getdis(u);
    tie(dv, pv) = getdis(v);
    vector<pii> us, vs;
    for(int i = 0; i < n; i++){
        if(du[i] < dv[i]) us.eb(mp(du[i], i));
        else vs.eb(mp(dv[i], i));
    }
    fill(iter(qry), 1);
    for(pii i : us) qry[pu[i.S]] = 0;
    for(pii i : vs) qry[pv[i.S]] = 0;
    qry[e] = 0;

    lsort(us);
    lsort(vs);

    auto owo = [qry, dis](vector<pii>& s, vector<int>& p){
        int l = 0, r = (int)s.size() - 1;
        while(l < r){
            int mid = (l + r + 1) / 2;
            vector<int> tmp = qry;
            for(int i = mid; i <= r; i++) tmp[p[s[i].S]] = 1;
//            cerr << "test " << l << " " << r << " " << mid << "\n";
            if(query(tmp) == dis) r = mid - 1;
            else l = mid;
        }
        return s[l].S;
    };

    int v1 = owo(us, pu);
    int v2 = owo(vs, pv);

//    cerr << v1 << " " << v2 << "\n";
    answer(v1, v2);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Correct 1 ms 200 KB Output is correct
9 Correct 1 ms 200 KB Output is correct
10 Correct 1 ms 200 KB Output is correct
11 Correct 1 ms 200 KB Output is correct
12 Correct 1 ms 200 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 15 ms 2016 KB Output is correct
3 Correct 144 ms 15856 KB Output is correct
4 Correct 148 ms 15924 KB Output is correct
5 Correct 150 ms 15860 KB Output is correct
6 Correct 140 ms 15812 KB Output is correct
7 Correct 147 ms 15916 KB Output is correct
8 Correct 145 ms 15880 KB Output is correct
9 Correct 140 ms 15860 KB Output is correct
10 Correct 139 ms 15856 KB Output is correct
11 Correct 148 ms 15168 KB Output is correct
12 Correct 147 ms 15296 KB Output is correct
13 Correct 156 ms 15068 KB Output is correct
14 Correct 147 ms 15040 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1992 KB Output is correct
2 Correct 26 ms 3536 KB Output is correct
3 Correct 37 ms 5132 KB Output is correct
4 Correct 117 ms 14976 KB Output is correct
5 Correct 111 ms 14988 KB Output is correct
6 Correct 112 ms 15340 KB Output is correct
7 Correct 110 ms 15056 KB Output is correct
8 Correct 111 ms 15156 KB Output is correct
9 Correct 109 ms 15324 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 456 KB Output is correct
2 Correct 17 ms 2016 KB Output is correct
3 Correct 111 ms 12688 KB Output is correct
4 Correct 137 ms 15860 KB Output is correct
5 Correct 145 ms 15884 KB Output is correct
6 Correct 138 ms 15804 KB Output is correct
7 Correct 144 ms 15888 KB Output is correct
8 Correct 135 ms 15860 KB Output is correct
9 Correct 143 ms 15880 KB Output is correct
10 Correct 153 ms 15964 KB Output is correct
11 Correct 148 ms 15076 KB Output is correct
12 Correct 154 ms 14984 KB Output is correct
13 Correct 160 ms 15392 KB Output is correct
14 Correct 154 ms 14840 KB Output is correct
15 Correct 143 ms 15860 KB Output is correct
16 Correct 137 ms 15880 KB Output is correct
17 Correct 150 ms 15032 KB Output is correct
18 Correct 149 ms 15068 KB Output is correct
19 Correct 152 ms 15876 KB Output is correct
20 Correct 146 ms 15216 KB Output is correct
21 Correct 126 ms 17040 KB Output is correct
22 Correct 124 ms 17040 KB Output is correct
23 Correct 129 ms 16680 KB Output is correct
24 Correct 134 ms 16536 KB Output is correct
25 Correct 154 ms 15212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1988 KB Output is correct
2 Correct 18 ms 2028 KB Output is correct
3 Correct 161 ms 16476 KB Output is correct
4 Correct 177 ms 16636 KB Output is correct
5 Correct 218 ms 17848 KB Output is correct
6 Correct 210 ms 17824 KB Output is correct
7 Correct 199 ms 18308 KB Output is correct
8 Correct 208 ms 18172 KB Output is correct
9 Correct 156 ms 11972 KB Output is correct
10 Correct 146 ms 11540 KB Output is correct
11 Correct 163 ms 13264 KB Output is correct
12 Correct 200 ms 16064 KB Output is correct
13 Correct 209 ms 17136 KB Output is correct
14 Correct 222 ms 17948 KB Output is correct
15 Correct 214 ms 18004 KB Output is correct
16 Correct 181 ms 13024 KB Output is correct
17 Correct 135 ms 16552 KB Output is correct
18 Correct 139 ms 16736 KB Output is correct
19 Correct 135 ms 16652 KB Output is correct
20 Correct 136 ms 16744 KB Output is correct
21 Correct 214 ms 17708 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2072 KB Output is correct
2 Correct 19 ms 2120 KB Output is correct
3 Correct 201 ms 16608 KB Output is correct
4 Correct 170 ms 16880 KB Output is correct
5 Correct 180 ms 16852 KB Output is correct
6 Correct 199 ms 18308 KB Output is correct
7 Correct 155 ms 16428 KB Output is correct
8 Correct 167 ms 16572 KB Output is correct
9 Correct 178 ms 16888 KB Output is correct
10 Correct 210 ms 18344 KB Output is correct
11 Correct 210 ms 18352 KB Output is correct
12 Correct 222 ms 18384 KB Output is correct
13 Correct 166 ms 13176 KB Output is correct
14 Correct 152 ms 11564 KB Output is correct
15 Correct 162 ms 13384 KB Output is correct
16 Correct 148 ms 11480 KB Output is correct
17 Correct 160 ms 13280 KB Output is correct
18 Correct 159 ms 11468 KB Output is correct
19 Correct 198 ms 16088 KB Output is correct
20 Correct 212 ms 16940 KB Output is correct
21 Correct 214 ms 17900 KB Output is correct
22 Correct 222 ms 17912 KB Output is correct
23 Correct 213 ms 18104 KB Output is correct
24 Correct 205 ms 17648 KB Output is correct
25 Correct 218 ms 17592 KB Output is correct
26 Correct 211 ms 18060 KB Output is correct
27 Correct 131 ms 16992 KB Output is correct
28 Correct 140 ms 16636 KB Output is correct
29 Correct 134 ms 16844 KB Output is correct
30 Correct 167 ms 16712 KB Output is correct
31 Correct 138 ms 16644 KB Output is correct
32 Correct 127 ms 16564 KB Output is correct
33 Correct 140 ms 16828 KB Output is correct
34 Correct 133 ms 16644 KB Output is correct
35 Correct 135 ms 16628 KB Output is correct
36 Correct 132 ms 16524 KB Output is correct
37 Correct 134 ms 16772 KB Output is correct
38 Correct 138 ms 17000 KB Output is correct
39 Correct 215 ms 18188 KB Output is correct
40 Correct 228 ms 17600 KB Output is correct
41 Correct 205 ms 17708 KB Output is correct
42 Correct 218 ms 17840 KB Output is correct