oj.uz

Submission #802806

# Submission time Handle Problem Language Result Execution time Memory
802806 2023-08-02T14:43:13 Z fatemetmhr Highway Tolls (IOI18_highway) C++17
5 / 100
 139 ms 15436 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;
int m, q[maxn5], par[maxn5], 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;
    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;
        }
    }
}

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);
    hi = 0; // pay attention, it've changed!!!!!!!!!!!!!!!!!!!
    par[hi] = -1;
    bfs(hi);
    //return;
    dfs(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(false && 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];
    answer(s, 0);
    return;
    //cout << "here " << lo << ' ' << hi << ' ' << s << endl;
    if(false && n > lim + 5){
        if(x == len * b){
            hi = lim;
            lo = -1;
        }
        else{
            lo = lim;
            hi = n - 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 * b)
            hi = mid;
        else
            lo = mid;
    }
    int v = s;
    bool re = false;
    while(v != -1){
        if(v == ver[hi])
            re = true;
        v = par[v];
    }
    int t;
    if(re)
        t = par[ver[hi]];
    else
        t = ver[hi];
    //cout << re << ' ' << hi << ' ' << lo << ' ' << t << endl;
    answer(s, t);
    return;

}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5968 KB Output is correct
2 Correct 9 ms 6760 KB Output is correct
3 Correct 101 ms 13056 KB Output is correct
4 Correct 139 ms 13028 KB Output is correct
5 Correct 75 ms 13012 KB Output is correct
6 Correct 92 ms 13136 KB Output is correct
7 Correct 100 ms 13008 KB Output is correct
8 Correct 74 ms 12996 KB Output is correct
9 Correct 85 ms 13008 KB Output is correct
10 Correct 88 ms 13064 KB Output is correct
11 Correct 122 ms 14708 KB Output is correct
12 Correct 86 ms 15436 KB Output is correct
13 Correct 102 ms 14856 KB Output is correct
14 Incorrect 80 ms 14176 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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