Submission #691897


Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <vector>
#include <set>
#include <queue>
#define SIZE 100005

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;

struct UF
{
	int par[SIZE],rank[SIZE];
	
	void init(int n)
	{
		for(int i=0;i<n;i++)
		{
			par[i]=i;
			rank[i]=0;
		}
	}
	int find(int x)
	{
		if(par[x]==x) return x;
		return par[x]=find(par[x]);
	}
	void unite(int x,int y)//x->y
	{
		x=find(x);
		y=find(y);
		if(x==y) return;
		par[x]=y;
	}
};
UF left,right;
//O(n*log^2n)
priority_queue <int,vector <int>, greater <int> > que[SIZE];
set <PP> mn;
set <PP>::iterator it;
bool use[SIZE];
int n;

void remL(int k)
{
	if(k>0)
	{
		int l=left.find(k-1);
		mn.erase(PP(que[k].top()+que[l].top(),P(l,k)));
	}
}
void remR(int k)
{
	int r=right.find(k)+1;
	if(r<n) mn.erase(PP(que[k].top()+que[r].top(),P(k,r)));
}
void remT(int k)
{
	if(que[k].size()>=2)
	{
		int s=que[k].top();que[k].pop();
		mn.erase(PP(s+que[k].top(),P(k,k)));
		que[k].push(s);
	}
}
void remX(int k)
{
	if(!use[k]||k==0) return;
	int l=left.find(k-1);
	int r=right.find(k)+1;
	if(r<n) mn.erase(PP(que[l].top()+que[r].top(),P(l,r)));
}
void rem(int k)
{
	remL(k),remR(k),remT(k),remX(k);
}
void insL(int k)
{
	if(k>0)
	{
		int l=left.find(k-1);
		mn.insert(PP(que[k].top()+que[l].top(),P(l,k)));
	}
}
void insR(int k)
{
	int r=right.find(k)+1;
	if(r<n) mn.insert(PP(que[k].top()+que[r].top(),P(k,r)));
}
void insT(int k)
{
	if(que[k].size()>=2)
	{
		int s=que[k].top();que[k].pop();
		mn.insert(PP(s+que[k].top(),P(k,k)));
		que[k].push(s);
	}
}
void insX(int k)
{
	if(!use[k]||k==0) return;
	int l=left.find(k-1);
	int r=right.find(k)+1;
	if(r<n) mn.insert(PP(que[l].top()+que[r].top(),P(l,r)));
}
void merge(int l,int r)//l<-r
{
	if(que[l].size()<que[r].size()) swap(que[l],que[r]);
	while(!que[r].empty())
	{
		que[l].push(que[r].top());
		que[r].pop();
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		int a;
		scanf("%d",&a);
		que[i].push(a);
	}
	left.init(n+2);
	right.init(n+2);
	for(int i=0;i+1<n;i++) insR(i);
	ll ret=0;
	for(int i=0;i+1<n;i++)
	{
		it=mn.begin();
		PP p=*it;mn.erase(it);
		ret+=p.first;
		int l=p.second.first,r=p.second.second;
		rem(l),rem(r);
		//printf("%d %d : %d\n",l,r,p.first);
		if(l==r)
		{
			que[l].pop();que[l].pop();
			que[l].push(p.first);
			insL(l);
			insR(l);
			insT(l);
			insX(l);
		}
		else
		{
			int m=-1,x=-1,y=-1;
			if(right.find(l)+1!=r)
			{
				m=right.find(l)+1;
				rem(m);
			}
			y=right.find(r)+1;
 			if(y<n&&use[y]) rem(y);
			else y=-1;
			if(l>0)
			{
				x=left.find(l-1);
				if(use[x]) rem(x);
				else x=-1;
			}
			//printf("* %d %d %d\n",m,x,y);
			left.unite(r,l);
			right.unite(l,r);
			que[l].pop();que[r].pop();merge(l,r);
			que[l].push(p.first);
			if(m!=-1)
			{
				left.unite(m,l);
				right.unite(m,r);
				merge(l,m);
			}
			if(y!=-1)
			{
				left.unite(y,l);
				right.unite(l,y);
				merge(l,y);
			}
			if(x!=-1)
			{
				left.unite(l,x);
				right.unite(x,l);
				merge(x,l);
				l=x;
			}
			use[l]=true;
			insL(l);
			insR(l);
			insT(l);
			insX(l);
		}
		//printf("[%d %d]\n",left.find(l),right.find(l));puts("");
	}
	printf("%lld\n",ret);
	return 0;
}

Submission Info

Submission Time
Task C - 最適二分探索木
User yutaka1999
Language C++14 (GCC 5.4.1)
Score 101
Code Size 3449 Byte
Status AC
Exec Time 511 ms
Memory 14720 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:122:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:126:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a);
                 ^

Judge Result

Set Name Sample Dataset1 Dataset2 Dataset3
Score / Max Score 0 / 0 50 / 50 50 / 50 1 / 1
Status
AC × 1
AC × 31
AC × 61
AC × 96
Set Name Test Cases
Sample 00_sample_01.txt
Dataset1 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt
Dataset2 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt, 02_00.txt, 02_01.txt, 02_02.txt, 02_03.txt, 02_04.txt, 02_05.txt, 02_06.txt, 02_07.txt, 02_08.txt, 02_09.txt, 02_10.txt, 02_11.txt, 02_12.txt, 02_13.txt, 02_14.txt, 02_15.txt, 02_16.txt, 02_17.txt, 02_18.txt, 02_19.txt, 02_20.txt, 02_21.txt, 02_22.txt, 02_23.txt, 02_24.txt, 02_25.txt, 02_26.txt, 02_27.txt, 02_28.txt, 02_29.txt
Dataset3 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt, 02_00.txt, 02_01.txt, 02_02.txt, 02_03.txt, 02_04.txt, 02_05.txt, 02_06.txt, 02_07.txt, 02_08.txt, 02_09.txt, 02_10.txt, 02_11.txt, 02_12.txt, 02_13.txt, 02_14.txt, 02_15.txt, 02_16.txt, 02_17.txt, 02_18.txt, 02_19.txt, 02_20.txt, 02_21.txt, 02_22.txt, 02_23.txt, 02_24.txt, 02_25.txt, 02_26.txt, 02_27.txt, 02_28.txt, 02_29.txt, 03_00.txt, 03_01.txt, 03_02.txt, 03_03.txt, 03_04.txt, 03_05.txt, 03_06.txt, 03_07.txt, 03_08.txt, 03_09.txt, 03_10.txt, 03_11.txt, 03_12.txt, 03_13.txt, 03_14.txt, 03_15.txt, 03_16.txt, 03_17.txt, 03_18.txt, 03_19.txt, 03_20.txt, 03_21.txt, 03_22.txt, 03_23.txt, 03_24.txt, 03_25.txt, 03_26.txt, 03_27.txt, 03_28.txt, 03_29.txt, 03_30.txt, 03_31.txt, 03_32.txt, 03_33.txt, 03_34.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 8 ms 3328 KB
01_00.txt AC 8 ms 3328 KB
01_01.txt AC 8 ms 3328 KB
01_02.txt AC 8 ms 3328 KB
01_03.txt AC 8 ms 3328 KB
01_04.txt AC 8 ms 3328 KB
01_05.txt AC 11 ms 3328 KB
01_06.txt AC 8 ms 3328 KB
01_07.txt AC 8 ms 3328 KB
01_08.txt AC 8 ms 3328 KB
01_09.txt AC 8 ms 3328 KB
01_10.txt AC 8 ms 3328 KB
01_11.txt AC 8 ms 3328 KB
01_12.txt AC 8 ms 3328 KB
01_13.txt AC 8 ms 3328 KB
01_14.txt AC 8 ms 3328 KB
01_15.txt AC 8 ms 3328 KB
01_16.txt AC 8 ms 3328 KB
01_17.txt AC 8 ms 3328 KB
01_18.txt AC 8 ms 3328 KB
01_19.txt AC 9 ms 3328 KB
01_20.txt AC 8 ms 3328 KB
01_21.txt AC 8 ms 3328 KB
01_22.txt AC 8 ms 3328 KB
01_23.txt AC 8 ms 3328 KB
01_24.txt AC 8 ms 3328 KB
01_25.txt AC 8 ms 3328 KB
01_26.txt AC 8 ms 3328 KB
01_27.txt AC 8 ms 3328 KB
01_28.txt AC 8 ms 3328 KB
01_29.txt AC 8 ms 3328 KB
02_00.txt AC 17 ms 3712 KB
02_01.txt AC 16 ms 3712 KB
02_02.txt AC 17 ms 3712 KB
02_03.txt AC 17 ms 3712 KB
02_04.txt AC 16 ms 3712 KB
02_05.txt AC 16 ms 3712 KB
02_06.txt AC 17 ms 3712 KB
02_07.txt AC 16 ms 3712 KB
02_08.txt AC 17 ms 3712 KB
02_09.txt AC 17 ms 3712 KB
02_10.txt AC 16 ms 3712 KB
02_11.txt AC 16 ms 3712 KB
02_12.txt AC 16 ms 3712 KB
02_13.txt AC 17 ms 3712 KB
02_14.txt AC 17 ms 3712 KB
02_15.txt AC 17 ms 3712 KB
02_16.txt AC 16 ms 3712 KB
02_17.txt AC 16 ms 3712 KB
02_18.txt AC 17 ms 3712 KB
02_19.txt AC 17 ms 3712 KB
02_20.txt AC 17 ms 3712 KB
02_21.txt AC 17 ms 3712 KB
02_22.txt AC 16 ms 3712 KB
02_23.txt AC 16 ms 3712 KB
02_24.txt AC 16 ms 3712 KB
02_25.txt AC 17 ms 3712 KB
02_26.txt AC 17 ms 3712 KB
02_27.txt AC 17 ms 3712 KB
02_28.txt AC 16 ms 3712 KB
02_29.txt AC 16 ms 3712 KB
03_00.txt AC 511 ms 14464 KB
03_01.txt AC 459 ms 14464 KB
03_02.txt AC 427 ms 14464 KB
03_03.txt AC 430 ms 14464 KB
03_04.txt AC 435 ms 14464 KB
03_05.txt AC 280 ms 14464 KB
03_06.txt AC 320 ms 14464 KB
03_07.txt AC 359 ms 14464 KB
03_08.txt AC 380 ms 14464 KB
03_09.txt AC 399 ms 14464 KB
03_10.txt AC 393 ms 14464 KB
03_11.txt AC 320 ms 14592 KB
03_12.txt AC 367 ms 14464 KB
03_13.txt AC 375 ms 14464 KB
03_14.txt AC 395 ms 14464 KB
03_15.txt AC 419 ms 14464 KB
03_16.txt AC 414 ms 14464 KB
03_17.txt AC 362 ms 14592 KB
03_18.txt AC 352 ms 14464 KB
03_19.txt AC 388 ms 14464 KB
03_20.txt AC 405 ms 14464 KB
03_21.txt AC 440 ms 14464 KB
03_22.txt AC 433 ms 14464 KB
03_23.txt AC 397 ms 14720 KB
03_24.txt AC 383 ms 14464 KB
03_25.txt AC 419 ms 14464 KB
03_26.txt AC 425 ms 14464 KB
03_27.txt AC 442 ms 14464 KB
03_28.txt AC 443 ms 14464 KB
03_29.txt AC 404 ms 14464 KB
03_30.txt AC 425 ms 14464 KB
03_31.txt AC 437 ms 14464 KB
03_32.txt AC 453 ms 14464 KB
03_33.txt AC 455 ms 14464 KB
03_34.txt AC 469 ms 14464 KB