Submission #114273

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
114273	2019-05-31T16:20:01 Z	faustaadp	Highway Tolls (IOI18_highway)	C++17	18 / 100	363 ms	44704 KB

highway

#include "highway.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll m,i,x[202020],y[202020],jarak,p[202020],te,o[202020];
vector<ll> v[202020],w[202020];
vector<int> z,q1,q2;
void dfs(ll aa,ll bb,ll cc)
{
	p[aa]=bb;
	//dep[aa]=cc;
	ll ii;
	for(ii=0;ii<v[aa].size();ii++)
		if(v[aa][ii]!=bb)
		{
			x[++te]=w[aa][ii];
			y[te]=v[aa][ii];
			o[w[aa][ii]]=v[aa][ii];
			dfs(v[aa][ii],aa,cc+1);
		}
}
void dfs1(ll aa)
{
	ll ii;
	for(ii=0;ii<v[aa].size();ii++)
		if(v[aa][ii]!=p[aa])
		{
		//	cout<<w[aa][ii]<<"_\n";
			z[w[aa][ii]]=0;
			dfs1(v[aa][ii]);
		}
}
void dfs2(ll aa,ll bb)
{
	ll ii;
	for(ii=0;ii<v[aa].size();ii++)
		if(v[aa][ii]!=p[aa])
		{
			if(bb==1)
			{
				q1.pb(w[aa][ii]);
			}
			dfs2(v[aa][ii],bb-1);
		}
}
void ubah(ll aa,ll bb,ll cc)
{
	ll ii;
	for(ii=aa;ii<=bb;ii++)
		z[x[ii]]=cc;
}
void ubah1(ll aa,ll bb,ll cc)
{
	ll ii;
	for(ii=aa;ii<=bb;ii++)
		z[q1[ii]]=cc;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) 
{
	m = U.size();
	for(i=0;i<m;i++)
	{
		v[U[i]].pb(V[i]);
		w[U[i]].pb(i);
		v[V[i]].pb(U[i]);
		w[V[i]].pb(i);
	}
	dfs(0,0,0);
	ll L=0,R=m-1,C,H;
	for(i=0;i<m;i++)
		z.pb(0);
	ll tem=ask(z);
	jarak=tem/A;
	ask(z);
	while(L<=R)
	{
		C=(L+R)/2;
		ubah(1,C,1);
		ubah(C+1,m,0);
		if(ask(z)==tem)
		{
			H=C+1;
			L=C+1;
		}
		else
			R=C-1;
	}
	ubah(1,m,1);
	z[x[H]]=0;
	dfs1(y[H]);	
	ll tom=ask(z);
	//for(i=0;i<m;i++)
	//	cout<<i<<" "<<z[i]<<"\n";
	//cout<<y	[H]<<" "<<H<<" "<<tom<<" "<<tem<<"\n";
	if(tom==tem)
	{
		if(jarak==1)
		{
			answer(y[H],p[y[H]]);
		}
		else
		{
			dfs2(y[H],jarak-1);
			L=0;
			R=q1.size()-1;
			//for(i=0;i<q1.size();i++)
			//	cout<<i<<"  "<<q1[i]<<"\n";
			ll H1;
			while(L<=R)
			{
				C=(L+R)/2;
				ubah1(0,C,0);
				ubah1(C+1,q1.size()-1,1);
				if(ask(z)==tem)
				{
					H1=C;
					R=C-1;
				}
				else
					L=C+1;
			}
			//cout<<H1<<"\n";
			//cout<<"A";
			//cout<<y[H]<<"_\n";
			//cout<<o[q1[H1]]<<" "<<p[y[H]]<<"\n";
			answer(o[q1[H1]],p[y[H]]);
		}
		//cout<<"A";
	}
	else
	{
		answer(0, N - 1);
	}
}

Compilation message

highway.cpp: In function 'void dfs(ll, ll, ll)':
highway.cpp:17:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
highway.cpp: In function 'void dfs1(ll)':
highway.cpp:29:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
highway.cpp: In function 'void dfs2(ll, ll)':
highway.cpp:40:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:130:18: warning: 'H1' may be used uninitialized in this function [-Wmaybe-uninitialized]
    answer(o[q1[H1]],p[y[H]]);
                  ^
highway.cpp:94:6: warning: 'H' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs1(y[H]); 
  ~~~~^~~~~~

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9848 KB	Output is correct
2	Correct	11 ms	9848 KB	Output is correct
3	Correct	10 ms	9808 KB	Output is correct
4	Correct	11 ms	9848 KB	Output is correct
5	Correct	10 ms	9740 KB	Output is correct
6	Correct	10 ms	9848 KB	Output is correct
7	Correct	11 ms	9848 KB	Output is correct
8	Correct	11 ms	9768 KB	Output is correct
9	Correct	11 ms	9848 KB	Output is correct
10	Correct	11 ms	9848 KB	Output is correct
11	Correct	10 ms	9720 KB	Output is correct
12	Correct	11 ms	9876 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	9944 KB	Output is correct
2	Correct	28 ms	11164 KB	Output is correct
3	Correct	265 ms	21384 KB	Output is correct
4	Correct	260 ms	21356 KB	Output is correct
5	Correct	296 ms	21336 KB	Output is correct
6	Correct	265 ms	21436 KB	Output is correct
7	Correct	279 ms	21500 KB	Output is correct
8	Correct	267 ms	21424 KB	Output is correct
9	Correct	275 ms	21396 KB	Output is correct
10	Correct	292 ms	21384 KB	Output is correct
11	Correct	243 ms	22172 KB	Output is correct
12	Correct	291 ms	23044 KB	Output is correct
13	Correct	285 ms	22444 KB	Output is correct
14	Correct	363 ms	21600 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	11932 KB	Output is correct
2	Correct	49 ms	13672 KB	Output is correct
3	Correct	71 ms	15244 KB	Output is correct
4	Correct	178 ms	25888 KB	Output is correct
5	Correct	166 ms	25884 KB	Output is correct
6	Correct	194 ms	26956 KB	Output is correct
7	Correct	206 ms	25876 KB	Output is correct
8	Correct	187 ms	26080 KB	Output is correct
9	Correct	164 ms	25880 KB	Output is correct