Submission #604952

#	Time	Username	Problem	Language	Result	Execution time	Memory
604952		Pyqe	ICC (CEOI16_icc)	C++14	100 / 100	104 ms	596 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
 
using namespace std;
 
long long n,nn[2],dsu[169],od[169];
bitset<169> kd;
int ca[2][169];
 
long long fd(long long x)
{
	if(dsu[x]!=x)
	{
		dsu[x]=fd(dsu[x]);
	}
	return dsu[x];
}
 
void run(int on)
{
	long long i,j,ii,k,c,c2,mk,mk2,e,e2,lh,rh,md,zz,z[2];
	
	n=on;
	for(i=1;i<=n;i++)
	{
		dsu[i]=i;
	}
	for(;1;)
	{
		c=0;
		for(i=1;i<=n;i++)
		{
			if(fd(i)==i)
			{
				od[i]=c;
				c++;
			}
		}
		if(c==1)
		{
			break;
		}
		mk=0;
		for(i=0;1ll<<i<c;i++)
		{
			for(ii=0;ii<2;ii++)
			{
				nn[ii]=0;
			}
			for(j=1;j<=n;j++)
			{
				kd[j]=od[fd(j)]>>i&1;
				ca[kd[j]][nn[kd[j]]]=j;
				nn[kd[j]]++;
			}
			k=query(nn[0],nn[1],ca[0],ca[1]);
			mk|=k<<i;
			if(k)
			{
				e=i;
			}
		}
		for(ii=0;ii<2;ii++)
		{
			nn[ii]=0;
		}
		c2=0;
		for(i=1;i<=n;i++)
		{
			kd[i]=od[fd(i)]>>e&1;
			ca[kd[i]][nn[kd[i]]]=i;
			nn[kd[i]]++;
			c2+=!kd[i]&&fd(i)!=i;
		}
		e=n-c-c2>c2;
		for(ii=0;ii<2;ii++)
		{
			e2=ii^e;
			for(zz=nn[e2],lh=1,rh=nn[e2]-1;lh<=rh;)
			{
				md=(lh+rh)/2;
				swap(nn[e2],md);
				k=query(nn[0],nn[1],ca[0],ca[1]);
				swap(nn[e2],md);
				if(k)
				{
					zz=md;
					rh=md-1;
				}
				else
				{
					lh=md+1;
				}
			}
			z[ii]=ca[e2][zz-1];
			if(!ii)
			{
				mk2=od[fd(z[ii])]^mk;
				nn[!e2]=0;
				for(i=1;i<=n;i++)
				{
					if(od[fd(i)]==mk2)
					{
						ca[!e2][nn[!e2]]=i;
						nn[!e2]++;
					}
				}
			}
		}
		setRoad(z[0],z[1]);
		dsu[fd(z[1])]=fd(z[0]);
	}
}

Compilation message (stderr)

icc.cpp: In function 'void run(int)':
icc.cpp:70:19: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |    kd[i]=od[fd(i)]>>e&1;
      |          ~~~~~~~~~^~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10