Submission #609448

#	Time	Username	Problem	Language	Result	Execution time	Memory
609448		AmirElarbi	Highway Tolls (IOI18_highway)	C++14	0 / 100	201 ms	262144 KiB

highway

#include <bits/stdc++.h>
#define vi vector<int>
#define gi greater<int>
#define gr greater
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e9
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 2e5+5
using namespace std;
const int MOD = 1e9+7;
const int nax = 1e5+5;
typedef complex<int> Point;
#define X real()
#define Y imag()
#include "highway.h"

vii adj[nax];
vi w;
int mxd= 0, dep[nax];
ii par[nax];
void dfs(int u, int p){
    for(auto x : adj[u]){
        if(x.fi == p) continue;
        dep[x.fi] = dep[u]+1;
        par[x.fi] = {u,x.se};
        mxd = max(mxd, dep[x.fi]);
        dfs(x.fi,u);
    }
}
void color(int u, int p){
    for(auto x : adj[u]){
        if(x.fi == p) continue;
        w[x.se] = 1;
        dfs(x.fi, u);
    }
}
void find_pair(int n, vi u, vi v, int a, int b) {
    int m = u.size();
    for (int i = 0; i < m; ++i)
    {
        adj[u[i]].pb({v[i],i});
        adj[v[i]].pb({u[i],i});
    }
    dep[0] = 0;
    dfs(0,0);
    vvi sm(mxd+1);
    w.assign(m,0);
    for (int i = 0; i < n; ++i)
    {
        sm[dep[i]].pb(i);
    }
    int totl = ask(w);
    int l = 0, r = mxd+1;
    while(l < r){
        w.clear();
        w.assign(m,0);
        int md = (l+r)/2;
        for(auto x : sm[md]){
            color(x,par[x].fi);
        }
        int qr = ask(w);
        if(qr == totl){
            r = md;
        } else {
            l = md+1;
        }
    }
    int dpanc = r;
    if(r == 0){
        answer(0,0);
        return;
    }
    l = 0, r = sm[dpanc].size();
    while(l< r){
        w.clear();
        w.assign(m,0);
        int md = (l+r)/2;
        for (int i = l; i <= md; ++i)
        {
            int u = sm[dpanc][i];
            w[par[u].se] = 1;
        }
        int qr = ask(w);
        if(qr==dpanc){
            l = md+1;
        } else {
            r = md;
        }
    }
    answer(0, sm[dpanc][r]);
}

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