oj.uz

Submission #114278

# Submission time Handle Problem Language Result Execution time Memory
114278 2019-05-31T16:33:41 Z faustaadp Highway Tolls (IOI18_highway) C++17
51 / 100
 318 ms 44708 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);
			//cout<<jer<<"\n";
			L=0;
			R=q1.size()-1;
			ubah(1,m,0);
			//for(i=0;i<q1.size();i++)
			//	cout<<q1[i]<<"*\n";
			while(L<=R)
			{
				C=(L+R)/2;
				ubah1(0,C,0);
				ubah1(C+1,q1.size()-1,1);
				if(ask(z)==tem)
				{
			//		cout<<C<<"_()\n";
					H1=o[q1[C]];
					R=C-1;
				}
				else
					L=C+1;
			}
		//	cout<<H1<<"\n";
		}
		ubah(1,m,0);
		dfs3(p[y[H]],jarak-jer,y[H]);
		L=0;
		R=q2.size()-1;
		//for(i=0;i<q2.size();i++)
		//	cout<<q2[i]<<"_\n";
		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;
		}
		//cout<<H1<<" "<<H2<<"\n";	
		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:195:9: warning: 'H2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   answer(H1, H2);
   ~~~~~~^~~~~~~~
highway.cpp:195: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 9848 KB Output is correct
2 Correct 11 ms 9848 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 9808 KB Output is correct
6 Correct 11 ms 9848 KB Output is correct
7 Correct 10 ms 9720 KB Output is correct
8 Correct 11 ms 9896 KB Output is correct
9 Correct 11 ms 9848 KB Output is correct
10 Correct 11 ms 9848 KB Output is correct
11 Correct 11 ms 9724 KB Output is correct
12 Correct 12 ms 9720 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9848 KB Output is correct
2 Correct 31 ms 11044 KB Output is correct
3 Correct 260 ms 21396 KB Output is correct
4 Correct 282 ms 21484 KB Output is correct
5 Correct 263 ms 21452 KB Output is correct
6 Correct 277 ms 21396 KB Output is correct
7 Correct 282 ms 21396 KB Output is correct
8 Correct 276 ms 21396 KB Output is correct
9 Correct 272 ms 21440 KB Output is correct
10 Correct 318 ms 21392 KB Output is correct
11 Correct 273 ms 22188 KB Output is correct
12 Correct 270 ms 23044 KB Output is correct
13 Correct 268 ms 22424 KB Output is correct
14 Correct 291 ms 21612 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11768 KB Output is correct
2 Correct 40 ms 13672 KB Output is correct
3 Correct 53 ms 15240 KB Output is correct
4 Correct 185 ms 25884 KB Output is correct
5 Correct 178 ms 25900 KB Output is correct
6 Correct 190 ms 26840 KB Output is correct
7 Correct 167 ms 25880 KB Output is correct
8 Correct 150 ms 26148 KB Output is correct
9 Correct 177 ms 25880 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9848 KB Output is correct
2 Correct 33 ms 11120 KB Output is correct
3 Correct 157 ms 18952 KB Output is correct
4 Correct 267 ms 21404 KB Output is correct
5 Correct 246 ms 21400 KB Output is correct
6 Correct 274 ms 21400 KB Output is correct
7 Correct 238 ms 21444 KB Output is correct
8 Correct 269 ms 21508 KB Output is correct
9 Correct 256 ms 21372 KB Output is correct
10 Correct 255 ms 21416 KB Output is correct
11 Correct 281 ms 21084 KB Output is correct
12 Correct 284 ms 23004 KB Output is correct
13 Correct 270 ms 22032 KB Output is correct
14 Correct 301 ms 22296 KB Output is correct
15 Correct 253 ms 21312 KB Output is correct
16 Correct 248 ms 21400 KB Output is correct
17 Correct 286 ms 22000 KB Output is correct
18 Correct 264 ms 21668 KB Output is correct
19 Correct 247 ms 21332 KB Output is correct
20 Correct 265 ms 22816 KB Output is correct
21 Correct 231 ms 22616 KB Output is correct
22 Correct 223 ms 22604 KB Output is correct
23 Correct 228 ms 22156 KB Output is correct
24 Correct 255 ms 22864 KB Output is correct
25 Correct 262 ms 27424 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 75 ms 43532 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 44708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -