제출 #114278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
114278		faustaadp	통행료 (IOI18_highway)	C++17	51 / 100	318 ms	44708 KiB

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 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);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31