Submission #802803

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
802803	2023-08-02T14:41:59 Z	fatemetmhr	Highway Tolls (IOI18_highway)	C++17	5 / 100	142 ms	20096 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);
    hi = 0;
    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	5884 KB	Output is correct
4	Correct	2 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	4 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	13 ms	6836 KB	Output is correct
3	Correct	105 ms	13072 KB	Output is correct
4	Correct	108 ms	13008 KB	Output is correct
5	Correct	93 ms	13048 KB	Output is correct
6	Correct	89 ms	13028 KB	Output is correct
7	Correct	101 ms	13068 KB	Output is correct
8	Correct	119 ms	13012 KB	Output is correct
9	Correct	142 ms	13112 KB	Output is correct
10	Correct	129 ms	13016 KB	Output is correct
11	Correct	89 ms	14760 KB	Output is correct
12	Correct	90 ms	15464 KB	Output is correct
13	Correct	101 ms	14860 KB	Output is correct
14	Incorrect	106 ms	14180 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	10 ms	7508 KB	Output is correct
2	Correct	18 ms	9192 KB	Output is correct
3	Correct	25 ms	10636 KB	Output is correct
4	Correct	109 ms	20068 KB	Output is correct
5	Correct	101 ms	20040 KB	Output is correct
6	Correct	83 ms	20028 KB	Output is correct
7	Correct	70 ms	20096 KB	Output is correct
8	Correct	79 ms	20076 KB	Output is correct
9	Incorrect	95 ms	20044 KB	Output is incorrect: {s, t} is wrong.
10	Halted	0 ms	0 KB	-