oj.uz

Submission #114276

# Submission time Handle Problem Language Result Execution time Memory
114276 2019-05-31T16:28:16 Z faustaadp Highway Tolls (IOI18_highway) C++17
18 / 100
 288 ms 44716 KB 
#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 dfs3(ll aa,ll bb,ll cc)
{
	ll ii;
	for(ii=0;ii<v[aa].size();ii++)
		if(v[aa][ii]!=p[aa]&&v[aa][ii]!=cc)
		{
			if(bb==1)
				q2.pb(w[aa][ii]);
			dfs3(v[aa][ii],bb-1,cc);
		}
}
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 ubah2(ll aa,ll bb,ll cc)
{
	ll ii;
	for(ii=aa;ii<=bb;ii++)
		z[q2[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;
			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;
			}
			answer(o[q1[H1]],p[y[H]]);
		}
		//cout<<"A";
	}
	else
	{
		ll jer=jarak-((tom-tem)/(B-A)),H1,H2;
		if(jer==1)
			H1=y[H];
		else
		{
			dfs2(y[H],jer-1);
			L=0;
			R=q1.size()-1;
			while(L<=R)
			{
				C=(L+R)/2;
				ubah1(0,C,0);
				ubah1(C+1,q1.size()-1,1);
				if(ask(z)==tem)
				{
					H1=o[q1[C]];
					R=C-1;
				}
				else
					L=C+1;
			}
		}
		ubah(1,m,0);
		dfs3(p[y[H]],jarak-jer,y[H]);
		L=0;
		R=q2.size()-1;
		while(L<=R)
		{
			C=(L+R)/2;
			ubah2(0,C,0);
			ubah2(C+1,q2.size()-1,1);
			if(ask(z)==tem)
			{
				H2=o[q2[C]];
				R=C-1;
			}
			else
				L=C+1;
		}
		answer(H1, H2);
	}
}

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 dfs3(ll, ll, ll)':
highway.cpp:53: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:186:9: warning: 'H2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   answer(H1, H2);
   ~~~~~~^~~~~~~~
highway.cpp:186:9: warning: 'H1' may be used uninitialized in this function [-Wmaybe-uninitialized]
highway.cpp:141:18: warning: 'H1' may be used uninitialized in this function [-Wmaybe-uninitialized]
    answer(o[q1[H1]],p[y[H]]);
                  ^
highway.cpp:111: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 11 ms 9720 KB Output is correct
2 Correct 11 ms 9876 KB Output is correct
3 Correct 11 ms 9720 KB Output is correct
4 Correct 11 ms 9848 KB Output is correct
5 Correct 11 ms 9768 KB Output is correct
6 Correct 11 ms 9848 KB Output is correct
7 Correct 10 ms 9848 KB Output is correct
8 Correct 10 ms 9768 KB Output is correct
9 Correct 11 ms 9848 KB Output is correct
10 Correct 10 ms 9848 KB Output is correct
11 Correct 11 ms 9720 KB Output is correct
12 Correct 11 ms 9768 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9976 KB Output is correct
2 Correct 33 ms 11128 KB Output is correct
3 Correct 282 ms 21392 KB Output is correct
4 Correct 288 ms 21460 KB Output is correct
5 Correct 280 ms 21412 KB Output is correct
6 Correct 260 ms 21412 KB Output is correct
7 Correct 279 ms 21412 KB Output is correct
8 Correct 283 ms 21400 KB Output is correct
9 Correct 246 ms 21376 KB Output is correct
10 Correct 270 ms 21364 KB Output is correct
11 Correct 276 ms 22240 KB Output is correct
12 Correct 277 ms 23120 KB Output is correct
13 Correct 282 ms 22440 KB Output is correct
14 Correct 259 ms 21624 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11836 KB Output is correct
2 Correct 37 ms 13772 KB Output is correct
3 Correct 69 ms 15324 KB Output is correct
4 Correct 188 ms 25892 KB Output is correct
5 Correct 173 ms 25940 KB Output is correct
6 Correct 189 ms 26952 KB Output is correct
7 Correct 180 ms 26012 KB Output is correct
8 Correct 197 ms 26096 KB Output is correct
9 Correct 175 ms 25880 KB Output is correct

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 43632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 73 ms 44716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -