oj.uz

Submission #604952

# Submission time Handle Problem Language Result Execution time Memory
604952 2022-07-25T11:07:29 Z Pyqe ICC (CEOI16_icc) C++14
100 / 100
 104 ms 596 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Ok! 99 queries used.
2 Correct 4 ms 468 KB Ok! 98 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 468 KB Ok! 517 queries used.
2 Correct 27 ms 596 KB Ok! 532 queries used.
3 Correct 33 ms 496 KB Ok! 529 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 480 KB Ok! 1282 queries used.
2 Correct 104 ms 476 KB Ok! 1278 queries used.
3 Correct 87 ms 480 KB Ok! 1253 queries used.
4 Correct 90 ms 468 KB Ok! 1268 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 480 KB Ok! 1251 queries used.
2 Correct 93 ms 476 KB Ok! 1253 queries used.
3 Correct 94 ms 476 KB Ok! 1273 queries used.
4 Correct 89 ms 468 KB Ok! 1270 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 480 KB Ok! 1259 queries used.
2 Correct 100 ms 476 KB Ok! 1270 queries used.
3 Correct 97 ms 468 KB Ok! 1270 queries used.
4 Correct 92 ms 468 KB Ok! 1274 queries used.
5 Correct 91 ms 468 KB Ok! 1271 queries used.
6 Correct 98 ms 468 KB Ok! 1296 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 476 KB Ok! 1258 queries used.
2 Correct 95 ms 484 KB Ok! 1274 queries used.