Submission #802817

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
802817	2023-08-02T14:49:38 Z	fatemetmhr	Highway Tolls (IOI18_highway)	C++17	18 / 100	144 ms	20444 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];
ll 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:137:9: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  137 |         if(x == len * b){
      |         ^~

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	6708 KB	Output is correct
2	Correct	3 ms	6704 KB	Output is correct
3	Correct	3 ms	6704 KB	Output is correct
4	Correct	4 ms	6704 KB	Output is correct
5	Correct	4 ms	6708 KB	Output is correct
6	Correct	4 ms	6736 KB	Output is correct
7	Correct	4 ms	6704 KB	Output is correct
8	Correct	3 ms	6704 KB	Output is correct
9	Correct	4 ms	6708 KB	Output is correct
10	Correct	3 ms	6660 KB	Output is correct
11	Correct	3 ms	6700 KB	Output is correct
12	Correct	3 ms	6736 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	6752 KB	Output is correct
2	Correct	13 ms	7624 KB	Output is correct
3	Correct	110 ms	13792 KB	Output is correct
4	Correct	107 ms	13804 KB	Output is correct
5	Correct	125 ms	13800 KB	Output is correct
6	Correct	132 ms	13792 KB	Output is correct
7	Correct	105 ms	13816 KB	Output is correct
8	Correct	84 ms	13788 KB	Output is correct
9	Correct	144 ms	13788 KB	Output is correct
10	Correct	116 ms	13776 KB	Output is correct
11	Correct	132 ms	15480 KB	Output is correct
12	Correct	93 ms	16232 KB	Output is correct
13	Correct	95 ms	15688 KB	Output is correct
14	Correct	105 ms	14948 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	8184 KB	Output is correct
2	Correct	19 ms	9688 KB	Output is correct
3	Correct	33 ms	11192 KB	Output is correct
4	Correct	72 ms	18156 KB	Output is correct
5	Correct	78 ms	18228 KB	Output is correct
6	Correct	97 ms	19464 KB	Output is correct
7	Correct	82 ms	20444 KB	Output is correct
8	Correct	68 ms	18752 KB	Output is correct
9	Correct	67 ms	19000 KB	Output is correct