Submission #295296

#	Time	Username	Problem	Language	Result	Execution time	Memory
295296		shayan_p	Highway Tolls (IOI18_highway)	C++17	51 / 100	344 ms	262148 KiB

highway

#include<bits/stdc++.h>
#include "highway.h"

#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k)) & 1)

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

vector<pii> v[maxn];

vector<int> vert, ids;
int h[maxn], par[maxn], parid[maxn];
ll len;
int A, B;

int ask2(vector<int> vec){
    ll num = ask(vec);
    return (num - len) / (B-A);
}
void fill(int u, int pr){
    vert.PB(u);
    for(auto [y, c] : v[u])
	if(y != pr){
	    h[y] = h[u] + 1;
	    par[y] = u;
	    parid[y] = c;
	    ids.PB(c);
	    fill(y, u);
	}
}

int solve(int m, int rt, int pr){
    vert.clear();
    ids.clear();
    h[rt] = 0;
    fill(rt, pr);

    vector<int> vec(m);
    for(int id : ids)
	vec[id] = 1;
    int H = ask2(vec);

    vector<int> lfs;
    for(int x : vert){
	if(h[x] == H){
	    lfs.PB(x);
	}
    }

    
    int l = 0, r = sz(lfs);
    while(r-l > 1){
	int mid = (l+r) >> 1;
	fill(vec.begin(), vec.end(), 0);
	for(int i = l; i < mid; i++){
	    int tmp = lfs[i];
	    while(tmp != rt && vec[parid[tmp]] == 0){
		vec[parid[tmp]] = 1;
		tmp = par[tmp];
	    }
	}
	
	if(ask2(vec) == H)
	    r = mid;
	else
	    l = mid;
    }

    return lfs[l];
}

void find_pair(int n, vector<int> U, vector<int> V, int A, int B){
    ::A = A, ::B = B;
    
    int m = sz(U);
    for(int i = 0; i < m; i++){
	v[U[i]].PB({V[i], i});
	v[V[i]].PB({U[i], i});
    }
    vector<int> vec(m);
    for(int &x : vec)
	x = 0;
    len = ask(vec);
    int l = 0, r = m;
    while(r-l > 1){
	int mid = (l+r) >> 1;
	for(int i = 0; i < m; i++)
	    vec[i] = 0;
	for(int i = l; i < mid; i++)
	    vec[i] = 1;
	if(ask(vec) > len)
	    r = mid;
	else
	    l = mid;
    }
    answer(solve(m, U[l], V[l]), solve(m, V[l], U[l]));    
}

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