Submission #372483

#	Time	Username	Problem	Language	Result	Execution time	Memory
372483		denkendoemeer	Highway Tolls (IOI18_highway)	C++14	100 / 100	300 ms	11460 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
int n,m,q[150005],h,ta,t[150005],viz[150005],p[150005],v2[150005];
vector<int>g,v3[150005];
void find_pair(int n2,vector<int>u,vector<int>v,int a,int b){
    int i;
    n=n2;
    m=u.size();
    g.resize(m);
    for(i=0;i<m;i++) {
        g[i]=0;
        v3[u[i]].push_back(v[i]);
        v3[v[i]].push_back(u[i]);
        }
    long long l=ask(g);
    int st=0,dr=n-2,mij,r=n-1;
    while(st<=dr){
        mij=(st+dr)/2;
        if (dr-st>60000)
            mij=60000;
        for(i=0;i<m;i++){
            if (u[i]>mij || v[i]>mij)
                g[i]=1;
            else
                g[i]=0;
        }
        if (ask(g)==l)
            r=mij,dr=mij-1;
        else
            st=mij+1;
    }
	int root=r;
	q[++ta]=root;
	viz[root]=1;
	t[root]=-1;
	while(h<ta){
		int x=q[++h];
		for(auto it:v3[x]){
			if (!viz[it]){
				viz[it]=1;
				q[++ta]=it;
				t[it]=x;
			}
		}
	}
	for(i=0;i<m;i++){
		if (t[u[i]]==v[i])
            p[u[i]]=i;
		if (t[v[i]]==u[i])
            p[v[i]]=i;
	}
	st=1;
	dr=ta-1;
	r=ta;
	while(st<=dr){
		mij=(st+dr)/2;
		if (dr-st>60000)
            mij=60000;
		for(i=0;i<m;i++)
            g[i]=1;
		for(i=2;i<=mij;i++)
            g[p[q[i]]]=0;
		if (ask(g)==l)
            r=mij,dr=mij-1;
		else
            st=mij+1;
	}
	int rb=q[r];
	int tp=rb;
	while(tp!=root){
		v2[p[tp]]=1;
		tp=t[tp];
	}
	st=1;
	dr=r-1;
	while(st<=dr){
		mij=(st+dr)/2;
		for(i=0;i<m;i++){
			if (!v2[i])
                g[i]=1;
			else
                g[i]=0;
		}
		for(i=2;i<=mij;i++)
            g[p[q[i]]]=0;
		if (ask(g)==l)
            r=mij,dr=mij-1;
		else
            st=mij+1;
	}
	int ra=q[r];
	answer(ra,rb);
}

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