Submission #802800

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
802800	2023-08-02T14:39:44 Z	fatemetmhr	Highway Tolls (IOI18_highway)	C++17	5 / 100	140 ms	19684 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;
    }
    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	5924 KB	Output is correct
2	Correct	4 ms	5988 KB	Output is correct
3	Correct	3 ms	5920 KB	Output is correct
4	Correct	4 ms	5920 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	5880 KB	Output is correct
9	Correct	3 ms	5924 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	3 ms	5968 KB	Output is correct
2	Correct	14 ms	6852 KB	Output is correct
3	Correct	90 ms	13016 KB	Output is correct
4	Correct	124 ms	13216 KB	Output is correct
5	Correct	116 ms	13020 KB	Output is correct
6	Correct	138 ms	13112 KB	Output is correct
7	Correct	120 ms	13068 KB	Output is correct
8	Correct	89 ms	13060 KB	Output is correct
9	Correct	140 ms	13068 KB	Output is correct
10	Correct	117 ms	13024 KB	Output is correct
11	Correct	88 ms	14748 KB	Output is correct
12	Correct	113 ms	15448 KB	Output is correct
13	Correct	106 ms	14908 KB	Output is correct
14	Incorrect	112 ms	14168 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	7504 KB	Output is correct
2	Correct	34 ms	8912 KB	Output is correct
3	Correct	33 ms	10404 KB	Output is correct
4	Correct	90 ms	17336 KB	Output is correct
5	Correct	67 ms	17460 KB	Output is correct
6	Correct	72 ms	18692 KB	Output is correct
7	Correct	101 ms	19684 KB	Output is correct
8	Correct	74 ms	17964 KB	Output is correct
9	Incorrect	92 ms	18256 KB	Output is incorrect: {s, t} is wrong.
10	Halted	0 ms	0 KB	-