Submission #802802

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
802802	2023-08-02T14:41:24 Z	fatemetmhr	Highway Tolls (IOI18_highway)	C++17	5 / 100	125 ms	19708 KB

highway

//  ~ 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);
    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];
    //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	5968 KB	Output is correct
3	Correct	3 ms	5964 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	5968 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	3 ms	5968 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	4 ms	5968 KB	Output is correct
2	Correct	12 ms	6740 KB	Output is correct
3	Correct	108 ms	13076 KB	Output is correct
4	Correct	101 ms	13012 KB	Output is correct
5	Correct	125 ms	13008 KB	Output is correct
6	Correct	116 ms	13016 KB	Output is correct
7	Correct	95 ms	13012 KB	Output is correct
8	Correct	111 ms	13012 KB	Output is correct
9	Correct	107 ms	13012 KB	Output is correct
10	Correct	88 ms	13044 KB	Output is correct
11	Correct	98 ms	14724 KB	Output is correct
12	Correct	117 ms	15488 KB	Output is correct
13	Correct	110 ms	14864 KB	Output is correct
14	Incorrect	106 ms	14172 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	Correct	9 ms	7376 KB	Output is correct
2	Correct	24 ms	8908 KB	Output is correct
3	Correct	33 ms	10404 KB	Output is correct
4	Correct	89 ms	17340 KB	Output is correct
5	Correct	94 ms	17504 KB	Output is correct
6	Correct	72 ms	18688 KB	Output is correct
7	Correct	85 ms	19708 KB	Output is correct
8	Correct	101 ms	18004 KB	Output is correct
9	Incorrect	92 ms	18232 KB	Output is incorrect: {s, t} is wrong.
10	Halted	0 ms	0 KB	-