oj.uz

Submission #1068252

# Submission time Handle Problem Language Result Execution time Memory
1068252 2024-08-21T08:51:28 Z Muhammad_Aneeq Highway Tolls (IOI18_highway) C++17
18 / 100
 120 ms 36944 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 divi1(int st,int en,int cnt)
{
	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 cos=ask(w);
	for (int i=st;i<=mid;i++)
		w[g[i]]=0;
	int f=(cos-dis)/(B1-A1);
	if (f)
		divi1(st,mid,f);
	if (cnt-f)
		divi1(mid+1,en,cnt-f);
}
void divi(int st,int en)
{
	for (auto i:g)
		w[i]=1;
	long long co=ask(w);
	for (auto i:g)
		w[i]=0;
	divi1(st,en,(co-dis)/(B1-A1));
}
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 4 ms 4952 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Correct 4 ms 4952 KB Output is correct
4 Correct 6 ms 4952 KB Output is correct
5 Correct 4 ms 4952 KB Output is correct
6 Correct 5 ms 4952 KB Output is correct
7 Correct 4 ms 5020 KB Output is correct
8 Correct 5 ms 4952 KB Output is correct
9 Correct 6 ms 4952 KB Output is correct
10 Correct 3 ms 4952 KB Output is correct
11 Correct 4 ms 4952 KB Output is correct
12 Correct 3 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 17 ms 5984 KB Output is correct
3 Correct 81 ms 13380 KB Output is correct
4 Correct 78 ms 13392 KB Output is correct
5 Correct 108 ms 13000 KB Output is correct
6 Correct 81 ms 12952 KB Output is correct
7 Correct 78 ms 12952 KB Output is correct
8 Correct 85 ms 13036 KB Output is correct
9 Correct 77 ms 12948 KB Output is correct
10 Correct 96 ms 12964 KB Output is correct
11 Correct 96 ms 14760 KB Output is correct
12 Correct 111 ms 15968 KB Output is correct
13 Correct 102 ms 15140 KB Output is correct
14 Correct 91 ms 14048 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 7008 KB Output is correct
2 Correct 21 ms 9176 KB Output is correct
3 Correct 35 ms 11088 KB Output is correct
4 Correct 76 ms 23104 KB Output is correct
5 Correct 105 ms 23104 KB Output is correct
6 Correct 75 ms 23104 KB Output is correct
7 Correct 88 ms 23112 KB Output is correct
8 Correct 89 ms 23100 KB Output is correct
9 Correct 76 ms 23104 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5208 KB Output is correct
2 Correct 13 ms 6048 KB Output is correct
3 Correct 60 ms 11336 KB Output is correct
4 Correct 97 ms 13012 KB Output is correct
5 Correct 78 ms 13004 KB Output is correct
6 Correct 92 ms 13216 KB Output is correct
7 Correct 93 ms 12924 KB Output is correct
8 Correct 77 ms 12968 KB Output is correct
9 Correct 92 ms 13036 KB Output is correct
10 Correct 86 ms 13008 KB Output is correct
11 Correct 98 ms 13916 KB Output is correct
12 Correct 113 ms 16000 KB Output is correct
13 Correct 100 ms 15164 KB Output is correct
14 Correct 98 ms 16128 KB Output is correct
15 Correct 90 ms 12956 KB Output is correct
16 Correct 88 ms 13132 KB Output is correct
17 Correct 120 ms 15480 KB Output is correct
18 Correct 111 ms 14700 KB Output is correct
19 Correct 99 ms 12924 KB Output is correct
20 Correct 103 ms 16804 KB Output is correct
21 Correct 91 ms 13804 KB Output is correct
22 Correct 77 ms 13796 KB Output is correct
23 Correct 104 ms 13664 KB Output is correct
24 Incorrect 100 ms 14540 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 57 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 33 ms 36944 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -