oj.uz

Submission #1068215

# Submission time Handle Problem Language Result Execution time Memory
1068215 2024-08-21T08:36:54 Z Muhammad_Aneeq Highway Tolls (IOI18_highway) C++17
18 / 100
 103 ms 36952 KB 
#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])
		{
			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;
		int q=z;
		while (q)
		{
			vector<int>g;
			for (auto i:ed[h[q]-1])
			{
				if (edges[i].second==q)
					continue;
				g.push_back(i);
			}
			ed[h[q]-1]=g;
			q=p[q];
		}
		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])
		{
			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 4 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 4952 KB Output is correct
6 Correct 4 ms 4952 KB Output is correct
7 Correct 4 ms 4952 KB Output is correct
8 Correct 4 ms 4964 KB Output is correct
9 Correct 4 ms 4952 KB Output is correct
10 Correct 7 ms 4952 KB Output is correct
11 Correct 6 ms 4952 KB Output is correct
12 Correct 4 ms 4952 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 14 ms 5980 KB Output is correct
3 Correct 101 ms 13024 KB Output is correct
4 Correct 85 ms 12976 KB Output is correct
5 Correct 87 ms 13128 KB Output is correct
6 Correct 88 ms 12964 KB Output is correct
7 Correct 83 ms 12940 KB Output is correct
8 Correct 85 ms 13076 KB Output is correct
9 Correct 77 ms 12964 KB Output is correct
10 Correct 94 ms 12956 KB Output is correct
11 Correct 91 ms 14756 KB Output is correct
12 Correct 102 ms 15968 KB Output is correct
13 Correct 103 ms 15460 KB Output is correct
14 Correct 96 ms 14272 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7256 KB Output is correct
2 Correct 23 ms 9176 KB Output is correct
3 Correct 35 ms 11096 KB Output is correct
4 Correct 81 ms 23376 KB Output is correct
5 Correct 77 ms 23112 KB Output is correct
6 Correct 84 ms 23508 KB Output is correct
7 Correct 76 ms 22992 KB Output is correct
8 Correct 93 ms 23108 KB Output is correct
9 Correct 78 ms 23120 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5208 KB Output is correct
2 Correct 12 ms 5976 KB Output is correct
3 Correct 67 ms 11460 KB Output is correct
4 Incorrect 92 ms 12932 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 67 ms 36944 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 36952 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -