Submission #394408

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
394408	2021-04-26T13:58:19 Z	Theo830	Highway Tolls (IOI18_highway)	C++17	6 / 100	300 ms	262148 KB

highway

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll INF = 1e18+7;
    ll MOD = 998244353;
    typedef pair<ll,ll> ii;
    #define iii pair<ll,ii>
    #define f(i,a,b) for(ll i = a;i < b;i++)
    #define pb push_back
    #define vll vector<ll>
    #define F first
    #define S second
    #define all(x) (x).begin(), (x).end()
    ///I hope I will get uprating and don't make mistakes
    ///I will never stop programming
    ///sqrt(-1) Love C++
    ///Please don't hack me
    ///@TheofanisOrfanou Theo830
    ///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
    ///Stay Calm
    ///Look for special cases
    ///Beware of overflow and array bounds
    ///Think the problem backwards
    ///Training
    #include "highway.h"
    ll par[90005] = {0};
    ll depth[90005] = {0};
    vector<vll>adj;
    void dfs(ll u,ll p){
        par[u] = p;
        for(auto x:adj[u]){
            if(x != p){
                depth[x] = depth[u] + 1;
                dfs(x,u);
            }
        }
    }
    void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B){
        adj.assign(N+1,vll());
        ll m = U.size();
        f(i,0,m){
            adj[U[i]].pb(V[i]);
            adj[V[i]].pb(U[i]);
        }
        dfs(0,-1);
        ll s = 0,t = 0;
        vector<int>w(m);
        w.assign(m,0);
        ll di = ask(w) / A;
        ll n = N;
        ll l = 0,r = n-2;
        while(l <= r){
            ll mid = (l+r)/2;
            w.assign(m,0);
            f(i,l,mid){
                w[i] = 1;
            }
            if(l == r){
                s = l;
                t = l+1;
                break;
            }
            ll g = ask(w);
            if(g == di * B){
                r = mid - 1;
            }
            else if(g == di * A){
                l = mid;
            }
            else{
                ll b = (g - (di * A)) / (B - A);
                ll a = di - b;
                s = mid - b;
                t = mid + a;
                break;
            }
        }
        answer(s,t);
    }

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	200 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	328 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	1608 KB	Output is correct
2	Correct	37 ms	2988 KB	Output is correct
3	Correct	32 ms	4388 KB	Output is correct
4	Correct	96 ms	12608 KB	Output is correct
5	Correct	140 ms	12516 KB	Output is correct
6	Correct	114 ms	12720 KB	Output is correct
7	Correct	138 ms	12580 KB	Output is correct
8	Correct	136 ms	12608 KB	Output is correct
9	Correct	135 ms	12620 KB	Output is correct