oj.uz

Submission #802858

# Submission time Handle Problem Language Result Execution time Memory
802858 2023-08-02T15:13:41 Z fatemetmhr Highway Tolls (IOI18_highway) C++17
51 / 100
 164 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;
    }
    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;
 
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:144:9: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  144 |         if(x <= (len - h[s]) * a + h[s] * b){
      |         ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6736 KB Output is correct
2 Correct 3 ms 6736 KB Output is correct
3 Correct 3 ms 6736 KB Output is correct
4 Correct 3 ms 6736 KB Output is correct
5 Correct 3 ms 6716 KB Output is correct
6 Correct 3 ms 6736 KB Output is correct
7 Correct 3 ms 6736 KB Output is correct
8 Correct 4 ms 6720 KB Output is correct
9 Correct 3 ms 6736 KB Output is correct
10 Correct 3 ms 6688 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 6864 KB Output is correct
2 Correct 9 ms 7648 KB Output is correct
3 Correct 79 ms 14508 KB Output is correct
4 Correct 109 ms 14504 KB Output is correct
5 Correct 101 ms 14560 KB Output is correct
6 Correct 102 ms 14508 KB Output is correct
7 Correct 103 ms 14492 KB Output is correct
8 Correct 101 ms 14504 KB Output is correct
9 Correct 114 ms 14508 KB Output is correct
10 Correct 96 ms 14564 KB Output is correct
11 Correct 107 ms 16292 KB Output is correct
12 Correct 112 ms 16976 KB Output is correct
13 Correct 126 ms 16396 KB Output is correct
14 Correct 109 ms 15700 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8272 KB Output is correct
2 Correct 16 ms 9856 KB Output is correct
3 Correct 33 ms 11432 KB Output is correct
4 Correct 69 ms 18828 KB Output is correct
5 Correct 78 ms 18932 KB Output is correct
6 Correct 115 ms 20104 KB Output is correct
7 Correct 93 ms 21168 KB Output is correct
8 Correct 81 ms 19448 KB Output is correct
9 Correct 94 ms 19776 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6864 KB Output is correct
2 Correct 14 ms 7688 KB Output is correct
3 Correct 78 ms 12936 KB Output is correct
4 Correct 98 ms 14536 KB Output is correct
5 Correct 83 ms 14528 KB Output is correct
6 Correct 101 ms 14512 KB Output is correct
7 Correct 94 ms 14528 KB Output is correct
8 Correct 115 ms 14488 KB Output is correct
9 Correct 117 ms 14568 KB Output is correct
10 Correct 92 ms 14536 KB Output is correct
11 Correct 108 ms 15712 KB Output is correct
12 Correct 140 ms 16464 KB Output is correct
13 Correct 116 ms 16000 KB Output is correct
14 Correct 107 ms 16892 KB Output is correct
15 Correct 120 ms 14548 KB Output is correct
16 Correct 99 ms 14508 KB Output is correct
17 Correct 136 ms 15792 KB Output is correct
18 Correct 121 ms 16720 KB Output is correct
19 Correct 113 ms 14496 KB Output is correct
20 Correct 99 ms 17232 KB Output is correct
21 Correct 82 ms 15128 KB Output is correct
22 Correct 98 ms 15132 KB Output is correct
23 Correct 94 ms 14948 KB Output is correct
24 Correct 103 ms 15404 KB Output is correct
25 Correct 117 ms 20400 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7724 KB Output is correct
2 Correct 19 ms 7772 KB Output is correct
3 Correct 109 ms 14944 KB Output is correct
4 Incorrect 164 ms 15276 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 19 ms 7636 KB Output is correct
2 Incorrect 16 ms 7764 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -