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
//  ~ 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){
      |         ^~
# 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
# 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
# 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
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 6792 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 7640 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 7588 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -