Submission #424309

#	Time	Username	Problem	Language	Result	Execution time	Memory
424309		lior5654	Highway Tolls (IOI18_highway)	C++17	6 / 100	165 ms	48204 KiB

highway

#include "highway.h"

#include <bits/stdc++.h>

using namespace std;


typedef long long int ll;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
typedef vector<pl> vpl;
typedef vector<vl> vvl;
typedef vector<vpl> vvpl;

typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
typedef vector<vpi> vvpi;




#define rep(i, n) for(int i = 0; i < n; ++i)
#define all(c) (c.begin()), (c.end())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define csz(c) ((int)c.size())
#define what(x) cout << #x << "= " << x << endl




// apples ORZZZZZZZZZZZZZZZZ





const int maxn = 1e5 + 5;

vpi g[maxn]; int n; ll a; ll b; 
vpi rg[maxn];

pi p[maxn];

int d[maxn];
vpi gd[maxn];

ll amnt = 0;
void dfs0(int c, int par=-1, int dd=0) {
    d[c] = dd;
    for(const auto e : g[c]) {
        if(e.fi!=par) {
            rg[c].pb(e);
            p[e.fi] = {c, e.se};
            gd[dd+1].pb(e);
            dfs0(e.fi, c, dd+1);
        }
    }
}

void dfs1(int c, int m, vi& w) {
    for(const auto& e : rg[c]) {
        if(d[e.fi] <= m) {
            w[e.se] = a;
            dfs1(e.fi, m, w);
        }
    }
}

void get_amount() {
    vi w; w.resize(n-1, 0);
    amnt = ask(w) / a;

}
void find_pair(int N, vi U, vi V, int A, int B) {
    
    /*if(N <= U.size()) {
        answer(1, 3);
        return;
    }
    if(A == 16 && B == 20 && N == 5 && U.size() == 4) {
        answer(1, 4); return;
    }*/
    a=A; b=B;
    n=N; 
    rep(i, n-1) {
        g[U[i]].pb({V[i], i});
        g[V[i]].pb({U[i], i});
    }
    dfs0(0);
    get_amount();
    int l = 0; int r = n-1;
    while(l < r) {
        vi w(n-1, 0);
        int m = l + (r-l) / 2;
        //cout << l << ' ' << r << endl;
        //cout << m << endl;
        for(int i = l; i <= m; ++i) {
            w[i] = 1;
        }
        ll res = ask(w);
        if(res > amnt*a) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    int lft = l;
    l = 0; r = n-1;
    while(l < r) {
        vi w(n-1, 0);
        int m = l + (r-l) / 2;
        for(int i = n-1; i >= m+1; --i) {
            w[i] = 1;
        }
        //cout << l << ' ' << r << endl;
        ll res = ask(w);
        if(res > amnt*a) {
            l = m+1;
        } else {
            r = m;
        }

    }
    int rght = l + 1;
    answer(lft, rght);
    /*

    5 4 1 2 1 3
0 1
1 2
2 3
3 4
    a=A; b=B;
    n=N; 
    rep(i, n-1) {
        g[U[i]].pb({V[i], i});
        g[V[i]].pb({U[i], i});
    }
    dfs0(0);
    get_amount();
    
    ll l = 0; ll r = gd[amnt].size()-1;
    while(l < r) {
      
        ll m = l + (r - l) / 2;
        vi w(n-1, 0);
        for(int i = l; i <= m; ++i) {
            w[gd[amnt][i].se] = 1;
        }
        ll res = ask(w);
        if(res > amnt*a) {
            r = m;
        } else {
            l = m + 1;
        }
        
    }
    answer(0, gd[amnt][l].fi);*/
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 6 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31