oj.uz

Submission #946704

# Submission time Handle Problem Language Result Execution time Memory
946704 2024-03-14T23:14:33 Z Edu175 Highway Tolls (IOI18_highway) C++17
11 / 100
 146 ms 18416 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*a)l=mid+1;
		else r=mid-1;
	}
	ll S=x;
	//cout<<r<<" r\n";
	fore(i,0,r){
		S=pa[S].fst;
	}
	/*s=vector<int>(m);
	paint(x,1);
	cout<<as*/
	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"<<lca<<"\n";
	// cout<<S<<" "<<E<<endl;
	answer(S,E); 
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 1 ms 5208 KB Output is correct
3 Correct 1 ms 5208 KB Output is correct
4 Correct 1 ms 5208 KB Output is correct
5 Correct 1 ms 5208 KB Output is correct
6 Correct 1 ms 5208 KB Output is correct
7 Correct 1 ms 5208 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 1 ms 5208 KB Output is correct
10 Correct 1 ms 5208 KB Output is correct
11 Correct 2 ms 4952 KB Output is correct
12 Correct 1 ms 5208 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5288 KB Output is correct
2 Correct 16 ms 6292 KB Output is correct
3 Correct 135 ms 12988 KB Output is correct
4 Correct 116 ms 12992 KB Output is correct
5 Correct 110 ms 12300 KB Output is correct
6 Correct 115 ms 12524 KB Output is correct
7 Correct 139 ms 12764 KB Output is correct
8 Correct 120 ms 12760 KB Output is correct
9 Correct 111 ms 12980 KB Output is correct
10 Correct 135 ms 12772 KB Output is correct
11 Incorrect 98 ms 14316 KB Output is incorrect: {s, t} is wrong.
12 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6696 KB Output is correct
2 Correct 16 ms 5432 KB Output is correct
3 Correct 23 ms 9260 KB Output is correct
4 Correct 81 ms 18248 KB Output is correct
5 Correct 75 ms 18416 KB Output is correct
6 Correct 93 ms 18188 KB Output is correct
7 Correct 76 ms 18184 KB Output is correct
8 Correct 80 ms 18264 KB Output is correct
9 Correct 107 ms 18348 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5288 KB Output is correct
2 Correct 9 ms 6080 KB Output is correct
3 Correct 94 ms 11460 KB Output is correct
4 Correct 87 ms 12520 KB Output is correct
5 Incorrect 146 ms 12524 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 6372 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 14 ms 6480 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -