oj.uz

Submission #946696

# Submission time Handle Problem Language Result Execution time Memory
946696 2024-03-14T22:46:29 Z Edu175 Highway Tolls (IOI18_highway) C++17
0 / 100
 147 ms 13196 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ggdem=b;i<ggdem;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define imp(v) for(auto messi:v)cout<<messi<<" "; cout<<"\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN=9e4+5;
vector<ii> g[MAXN];
ii pa[MAXN];
ll vis[MAXN],D[MAXN];
vector<int>s,h;
void dfs(ll x){
	vis[x]=1;
	for(auto [y,i]:g[x])if(!vis[y]){
		pa[y]={x,i};
		D[y]=D[x]+1;
		dfs(y);
	}
	if(SZ(g[x])==1&&g[x][0].fst==pa[x].fst)h.pb(x);
}

ll n;
void paint(ll x, ll r=n){
	fore(i,0,r){
		if(pa[x].fst==-1||s[pa[x].snd]==1)break;
		s[pa[x].snd]=1;
		x=pa[x].fst;
	}
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	int M = U.size();
	ll m=M,a=A,b=B;
	n=N;
	s.resize(m);
	fore(i,0,m){
		g[U[i]].pb({V[i],i});
		g[V[i]].pb({U[i],i});
	}
	srand(175);
	ll rt=rand()%n;
	pa[rt]={-1,-1};
	D[rt]=0;
	dfs(rt);
	ll d=ask(s)/a;
	//cout<<rt<<endl;
	//imp(h);
	ll l=0,r=SZ(h)-1;
	while(l<=r){
		ll mid=(l+r)/2;
		s=vector<int>(m);
		fore(i,0,mid+1)paint(h[i]);
		if(ask(s)<d*b)l=mid+1;
		else r=mid-1;
	}
	ll x=h[l];
	l=0,r=SZ(h)-1;
	while(l<=r){
		ll mid=(l+r)/2;
		s=vector<int>(m);
		fore(i,mid,SZ(h))paint(h[i]);
		if(ask(s)<d*b)r=mid-1;
		else l=mid+1;
	}
	ll y=h[r];
	l=0,r=D[x];
	while(l<=r){
		ll mid=(l+r)/2;
		s=vector<int>(m);
		paint(x,mid);
		if(ask(s)==d)l=mid+1;
		else r=mid-1;
	}
	ll S=x;
	fore(i,0,r){
		S=pa[S].fst;
	}
	s=vector<int>(n);
	for(ll y=S;y>=0;y=pa[y].fst){
		s[y]=1;
	}
	ll lca=y;
	for(ll i=y;i>=0;i=pa[i].fst){
		if(s[i]){lca=i;break;}
	}
	ll E=-1;
	if(x==y){
		ll v=S;
		fore(j,0,d)v=pa[v].fst;
		E=v;
		//cout<<"ig \n";
	}
	else {
		for(ll i=y;i>=0;i=pa[i].fst){
			if(D[i]==d-(D[S]-D[lca])+D[lca]){E=i;break;}
		}
	}
	//cout<<x<<" "<<y<<"\n";
	//cout<<S<<" "<<E<<endl;
	answer(S,E); 
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Correct 1 ms 4952 KB Output is correct
4 Incorrect 1 ms 5208 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5288 KB Output is correct
2 Correct 13 ms 6272 KB Output is correct
3 Correct 114 ms 12984 KB Output is correct
4 Incorrect 147 ms 13196 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6696 KB Output is correct
2 Incorrect 27 ms 7580 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5288 KB Output is correct
2 Correct 10 ms 6056 KB Output is correct
3 Incorrect 75 ms 11468 KB Output is incorrect: {s, t} is wrong.
4 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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