Submission #114272

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
114272	2019-05-31T16:18:40 Z	faustaadp	Highway Tolls (IOI18_highway)	C++17	6 / 100	226 ms	44716 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))
				{
					H1=C;
					L=C+1;
				}
				else
					R=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
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	10 ms	9848 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	11 ms	9848 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	11780 KB	Output is correct
2	Correct	45 ms	13764 KB	Output is correct
3	Correct	70 ms	15356 KB	Output is correct
4	Correct	184 ms	25884 KB	Output is correct
5	Correct	226 ms	26004 KB	Output is correct
6	Correct	187 ms	26932 KB	Output is correct
7	Correct	192 ms	25936 KB	Output is correct
8	Correct	218 ms	26064 KB	Output is correct
9	Correct	181 ms	25876 KB	Output is correct