Submission #802797

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
802797	2023-08-02T14:37:21 Z	fatemetmhr	Highway Tolls (IOI18_highway)	C++17	5 / 100	139 ms	19736 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(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(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;

}

Compilation message

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

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	5968 KB	Output is correct
4	Correct	3 ms	5920 KB	Output is correct
5	Correct	3 ms	5920 KB	Output is correct
6	Correct	4 ms	5928 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	3 ms	6068 KB	Output is correct
2	Correct	13 ms	6736 KB	Output is correct
3	Correct	88 ms	13012 KB	Output is correct
4	Correct	128 ms	13016 KB	Output is correct
5	Correct	83 ms	13064 KB	Output is correct
6	Correct	139 ms	13056 KB	Output is correct
7	Correct	88 ms	13012 KB	Output is correct
8	Correct	116 ms	13068 KB	Output is correct
9	Correct	130 ms	13016 KB	Output is correct
10	Correct	106 ms	13016 KB	Output is correct
11	Correct	111 ms	14696 KB	Output is correct
12	Correct	103 ms	15524 KB	Output is correct
13	Correct	113 ms	14852 KB	Output is correct
14	Incorrect	124 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	7504 KB	Output is correct
2	Correct	24 ms	8904 KB	Output is correct
3	Correct	39 ms	10408 KB	Output is correct
4	Correct	102 ms	17340 KB	Output is correct
5	Correct	67 ms	17460 KB	Output is correct
6	Correct	100 ms	18628 KB	Output is correct
7	Correct	70 ms	19736 KB	Output is correct
8	Correct	107 ms	17960 KB	Output is correct
9	Incorrect	100 ms	18276 KB	Output is incorrect: {s, t} is wrong.
10	Halted	0 ms	0 KB	-