oj.uz

Submission #802866

# Submission time Handle Problem Language Result Execution time Memory
802866 2023-08-02T15:18:13 Z fatemetmhr Highway Tolls (IOI18_highway) C++17
51 / 100
 165 ms 21168 KB 
//  ~ Be Name Khoda ~  //
 
#include "highway.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
 
using namespace std;
 
typedef long long ll;
 
#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
 
const int maxn  =  1e6   + 10;
const int maxn5 =  2e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;
 
vector <int> tok, adj[maxn5], v, u, ver, ed;
ll len, h[maxn5];
int m, q[maxn5], par[maxn5];
ll pas[maxn5];
bool mark[maxn5], good[maxn5];
 
void bfs(int rt){
    par[rt] = -1;
    memset(mark, false, sizeof mark);
    int l = 0, r = 1;
    q[0] = rt;
    mark[rt] = true;
    h[rt] = 0;
    while(l < r){
        int a = q[l++];
        for(auto id : adj[a]){
            int b = u[id] == a ? v[id] : u[id];
            if(mark[b])
                continue;
            //cout << "here " << a << ' ' << b << ' ' << id << endl;
            good[id] = true;
            mark[b] = true;
            q[r++] = b;
            par[b] = a;
            h[b] = h[a] + 1;
        }
    }
}
 
void dfs(int v){
    //cout << v << ' ' << par[v] << endl;
    for(auto id : adj[v]) if(good[id]){
        int u = (::u[id]) == v ? (::v[id]) : (::u[id]);
        if(u == par[v])
            continue;
        //cout << "in " << v << ' ' << u << ' ' << id << endl;
        dfs(u);
        ver.pb(u);
        ed.pb(id);
    }
}
 
ll get(int id){
    if(pas[id] == -1){
        fill(all(tok), 1);
        for(auto u : ed)
            tok[u] = false;
        for(int i = 0; i <= id; i++)
            tok[ed[i]] = true;
        pas[id] = ask(tok);
    }
    return pas[id];
}
 
 
void find_pair(int n, std::vector<int> U, std::vector<int> V, int a, int b){
    memset(pas, -1, sizeof pas);
    u = U;
    v = V;
    m = u.size();
    for(int i = 0; i < m; i++){
        adj[u[i]].pb(i);
        adj[v[i]].pb(i);
    }
    int lo = -1, hi = n;
    tok.resize(m);
    fill(all(tok), 0);
    len = ask(tok) / a;
    while(hi - lo > 1){
        int mid = (lo + hi) >> 1;
        fill(all(tok), 0);
        for(int i = 0; i <= mid; i++)
            for(auto id : adj[i])
                tok[id] = 1;
        ll cost = ask(tok);
        if(cost == len * a)
            lo = mid;
        else
            hi = mid;
    }
    assert(hi < n);
    par[hi] = -1;
    bfs(hi);
    //return;
    dfs(hi);
    int rt = hi;
    /*
    for(int i = 0; i < n - 1; i++)
        cout << ed[i] << ' ' << ver[i] << endl;
    //*/
    //cout << "its " << hi << endl;
    lo = -1; hi = n - 1;
    ll x;
    int lim = 60000;
    if(n > lim + 5){
        x = get(lim);
        if(x == len * a){
            lo = lim;
            hi = n - 1;
        }
        else{
            lo = -1;
            hi = lim;
        }
    }
    while(hi - lo > 1){
        int mid = (lo + hi) >> 1;
        if(get(mid) == len * a)
            lo = mid;
        else
            hi = mid;
    }
    int s = ver[hi];
    if(h[s] == len){
        answer(s, rt);
        return;
    }
    //cout << "here " << lo << ' ' << hi << ' ' << s << endl;
    if(n > lim + 5){
        if(x <= (len - h[s]) * a + h[s] * b){
            lo = lim;
            hi = n - 1;
        }
        else{
            hi = lim;
            lo = -1;
        }
    }
    else{
        lo = -1;
        hi = n - 1;
    }
    while(hi - lo > 1){
        int mid = (lo + hi) >> 1;
        //cout << mid << ' ' << get(mid) << ' ' << len << ' ' << a << ' ' << b << endl;
        if(get(mid) <= (len - h[s]) * a + h[s] * b)
            lo = mid;
        else
            hi = mid;
    }
    //cout << re << ' ' << hi << ' ' << lo << ' ' << t << endl;
    answer(s, ver[hi]);
    return;
 
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6772 KB Output is correct
2 Correct 13 ms 7696 KB Output is correct
3 Correct 98 ms 14504 KB Output is correct
4 Correct 98 ms 14548 KB Output is correct
5 Correct 127 ms 14524 KB Output is correct
6 Correct 86 ms 14576 KB Output is correct
7 Correct 83 ms 14564 KB Output is correct
8 Correct 88 ms 14560 KB Output is correct
9 Correct 84 ms 14500 KB Output is correct
10 Correct 103 ms 14524 KB Output is correct
11 Correct 116 ms 16180 KB Output is correct
12 Correct 96 ms 16996 KB Output is correct
13 Correct 115 ms 16384 KB Output is correct
14 Correct 101 ms 15708 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8280 KB Output is correct
2 Correct 15 ms 9852 KB Output is correct
3 Correct 32 ms 11428 KB Output is correct
4 Correct 83 ms 18892 KB Output is correct
5 Correct 85 ms 19060 KB Output is correct
6 Correct 90 ms 20112 KB Output is correct
7 Correct 70 ms 21168 KB Output is correct
8 Correct 65 ms 19440 KB Output is correct
9 Correct 69 ms 19764 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6824 KB Output is correct
2 Correct 15 ms 7636 KB Output is correct
3 Correct 96 ms 12944 KB Output is correct
4 Correct 112 ms 14496 KB Output is correct
5 Correct 87 ms 14556 KB Output is correct
6 Correct 100 ms 14528 KB Output is correct
7 Correct 109 ms 14520 KB Output is correct
8 Correct 121 ms 14508 KB Output is correct
9 Correct 93 ms 14532 KB Output is correct
10 Correct 105 ms 14500 KB Output is correct
11 Correct 117 ms 15712 KB Output is correct
12 Correct 131 ms 16500 KB Output is correct
13 Correct 108 ms 16000 KB Output is correct
14 Correct 110 ms 16832 KB Output is correct
15 Correct 128 ms 14488 KB Output is correct
16 Correct 93 ms 14556 KB Output is correct
17 Correct 96 ms 15932 KB Output is correct
18 Correct 118 ms 16724 KB Output is correct
19 Correct 83 ms 14560 KB Output is correct
20 Correct 88 ms 17176 KB Output is correct
21 Correct 79 ms 15128 KB Output is correct
22 Correct 105 ms 15116 KB Output is correct
23 Correct 120 ms 14956 KB Output is correct
24 Correct 132 ms 15428 KB Output is correct
25 Correct 99 ms 20464 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7828 KB Output is correct
2 Correct 15 ms 7760 KB Output is correct
3 Correct 109 ms 14896 KB Output is correct
4 Incorrect 165 ms 15284 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 7728 KB Output is correct
2 Incorrect 17 ms 7652 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -