Submission #1068187

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1068187	2024-08-21T08:21:49 Z	Muhammad_Aneeq	Highway Tolls (IOI18_highway)	C++17	18 / 100	115 ms	37164 KB

highway

#include <vector>
#include <iostream>
#include <map>
#include "highway.h"
using namespace std;
int const MAXN=1e5;
vector<int>w;
long long dis=0;
vector<pair<int,int>>nei[MAXN]={};
int B1,A1;
vector<pair<int,int>>edges;
vector<int>ed[MAXN]={};
int h[MAXN]={};
int p[MAXN]={};
vector<int>d;
vector<int>g;
int it[MAXN],ot[MAXN];
int tm=0;
void dfs(int u,int pa=-1)
{
	it[u]=tm++;
	p[u]=pa;
	for (auto [i,in]:nei[u])
	{
		if (i==pa)
			continue;
		ed[h[u]].push_back(in);
		h[i]=h[u]+1;
		dfs(i,u);
	}
	ot[u]=tm-1;
}
bool check(int mid)
{
	for (int i=mid;i<MAXN;i++)
	{
		for (auto j:ed[i])
			w[j]=1;
	}
	long long g=ask(w);
	for (int i=mid;i<MAXN;i++)
	{
		for (auto j:ed[i])
			w[j]=0;
	}
	return (g!=dis);
}
bool check1(int mid,int z)
{
	for (int i=mid;i<MAXN;i++)
	{
		for (auto j:ed[i])
		{
			int x=edges[j].first;
			if (it[x]<=it[z]&&ot[x]>=ot[z])
				continue;
			w[j]=1;
		}
	}
	long long g=ask(w);
	for (int i=mid;i<MAXN;i++)
	{
		for (auto j:ed[i])
			w[j]=0;
	}
	return (g!=dis);	
}
void divi(int st,int en)
{
	if (st==en)
	{
		d.push_back(g[en]);
		return;
	}
	int mid=(st+en)/2;
	for (int i=st;i<=mid;i++)
		w[g[i]]=1;
	long long co=ask(w);
	for (int i=st;i<=mid;i++)
		w[g[i]]=0;
	if (co>dis)
		divi(st,mid);
	for (int i=mid+1;i<=en;i++)
		w[g[i]]=1;
	co=ask(w);
	for (int i=mid+1;i<=en;i++)
		w[g[i]]=0;
	if (co>dis)
		divi(mid+1,en);
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
	A1=A,B1=B;
	int m=U.size();
	for (int i=0;i<m;i++)
	{
		nei[U[i]].push_back({V[i],i});
		nei[V[i]].push_back({U[i],i});
	}
	dfs(0);
	for (int i=0;i<m;i++)
	{
		if (h[U[i]]>h[V[i]])
			swap(U[i],V[i]);
		edges.push_back({U[i],V[i]});
	}
	w.resize(m,0);
	dis=ask(w);
	h[0]=0;
	int st=0,en=N;
	while (st+1<en)
	{
		int mid=(st+en)/2;
		if (check(mid))
			st=mid;
		else
			en=mid;
	}
	for (auto i:ed[st])
		g.push_back(i);
	divi(0,g.size()-1);
	if (d.size()==2)
	{
		answer(edges[d[0]].second,edges[d[1]].second);
	}
	else
	{
		en=st;
		st=-1;
		int z=edges[d[0]].second;
		while (st+1<en)
		{
			int mid=(st+en)/2;
			if (check1(mid,z))
				st=mid;
			else
				en=mid;
		}
		if (st==-1)
		{
			int len=dis/A;
			int x=z;
			while (len--)
				x=p[x];
			answer(z,x);
			return;
		}
		d={};
		g={};
		for (auto i:ed[st])
		{
			int x=edges[i].first;
			if (it[x]<=it[z]&&ot[x]>=ot[z])
				continue;
			g.push_back(i);
		}
		divi(0,g.size()-1);
		answer(z,edges[d[0]].second);
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	5208 KB	Output is correct
2	Correct	12 ms	5976 KB	Output is correct
3	Correct	87 ms	12996 KB	Output is correct
4	Correct	88 ms	12972 KB	Output is correct
5	Correct	90 ms	12920 KB	Output is correct
6	Correct	96 ms	12944 KB	Output is correct
7	Correct	86 ms	12956 KB	Output is correct
8	Correct	88 ms	13280 KB	Output is correct
9	Correct	81 ms	12964 KB	Output is correct
10	Correct	90 ms	12956 KB	Output is correct
11	Correct	95 ms	14844 KB	Output is correct
12	Correct	115 ms	15884 KB	Output is correct
13	Correct	103 ms	15612 KB	Output is correct
14	Correct	100 ms	14040 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	7000 KB	Output is correct
2	Correct	23 ms	9176 KB	Output is correct
3	Correct	25 ms	11136 KB	Output is correct
4	Correct	80 ms	23112 KB	Output is correct
5	Correct	79 ms	23116 KB	Output is correct
6	Correct	82 ms	23112 KB	Output is correct
7	Correct	75 ms	23540 KB	Output is correct
8	Correct	85 ms	23112 KB	Output is correct
9	Correct	77 ms	23108 KB	Output is correct