oj.uz

답안 #234642

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
234642 2020-05-25T01:15:30 Z mahmoudbadawy Zamjene (COCI16_zamjene) C++17
0 / 140
 2503 ms 90092 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=1e6+6,H=2,BASE=N;
const int MOD[H]={(int)1e9+7,(int)1e9+9};
int pw[N][H];
map< pair<int,int>, int > mp;
long long ans4,bad;
int arr[N],sor[N];

inline int neg(int x,int i)
{
	x=MOD[i]-x;
	if(x>=MOD[i]) return x-MOD[i];
	return x;
}

struct DSU{
	int pa[N],sz[N];
	int hsh[N][H];	void init(int n)
	{
		iota(pa,pa+n,0);
		fill(sz,sz+n,1);
	}
	int operator() (int x)
	{
		if(pa[x]==x) return x;
		return pa[x]=(*this)(pa[x]);
	}
	void operator() (int x,int y)
	{
		x=(*this)(x); y=(*this)(y);
		if(x==y) return;
		if(sz[x]>sz[y]) swap(x,y);
		if(hsh[x][0]||hsh[x][1]) {bad--; mp[{hsh[x][0],hsh[x][1]}]-=sz[x]; ans4-=1LL*mp[{neg(hsh[x][0],0),neg(hsh[x][1],1)}]*sz[x]; }
		if(hsh[y][0]||hsh[y][1]) {bad--; mp[{hsh[y][0],hsh[y][1]}]-=sz[y]; ans4-=1LL*mp[{neg(hsh[y][0],0),neg(hsh[y][1],1)}]*sz[y]; }
		for(int i=0;i<H;i++)
		{
			hsh[y][i]+=hsh[x][i];
			hsh[y][i]%=MOD[i];
			hsh[y][i]+=MOD[i];
			while(hsh[y][i]>=MOD[i]) hsh[y][i]-=MOD[i];
		}
		pa[x]=y; sz[y]+=sz[x]; sz[x]=0;
		if(hsh[y][0]||hsh[y][1]) {bad++; ans4+=1LL*mp[{neg(hsh[y][0],0),neg(hsh[y][1],1)}]*sz[y]; mp[{hsh[y][0],hsh[y][1]}]+=sz[y];}
	}
	void mod(int x,int y,int z)
	{
		x=(*this)(x);
		if(hsh[x][0]||hsh[x][1]) {bad--; ans4-=1LL*mp[{neg(hsh[x][0],0),neg(hsh[x][1],1)}]*sz[x]; mp[{hsh[x][0],hsh[x][1]}]-=sz[x];}
		for(int i=0;i<H;i++)
		{
			hsh[x][i]+=pw[y][i];
			hsh[x][i]-=pw[z][i];
			hsh[x][i]%=MOD[i];
			hsh[x][i]+=MOD[i];
			while(hsh[x][i]>=MOD[i]) hsh[x][i]-=MOD[i];
		}
		if(hsh[x][0]||hsh[x][1]) {bad++; ans4+=1LL*mp[{neg(hsh[x][0],0),neg(hsh[x][1],1)}]*sz[x]; mp[{hsh[x][0],hsh[x][1]}]+=sz[x];}
	}
} dsu;

void print()
{
	return;
	cout << "DATA: " << endl;
	for(int i=0;i<4;i++)
	{
		cout << dsu(i) << endl;
		cout << dsu.hsh[i][0] << " " << dsu.hsh[i][1] << endl;
		cout << dsu.sz[i] << " " << mp[{neg(dsu.hsh[i][0],0),neg(dsu.hsh[i][1],1)}] << endl;
	}
}

int main()
{
	pw[0][0]=pw[0][1]=1;
	for(int i=1;i<N;i++)
	{
		for(int j=0;j<H;j++)
			pw[i][j]=(1LL*BASE*pw[i-1][j])%MOD[j];
	}
	int n,q;
	scanf("%d %d",&n,&q);
	dsu.init(n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&arr[i]);
		sor[i]=arr[i];
	}
	sort(sor,sor+n);
	for(int i=0;i<n;i++)
	{
		dsu.mod(i,arr[i],sor[i]);
	}
	while(q--)
	{
		print();
		int t;
		scanf("%d",&t);
		if(t==2)
		{
			int x,y;
			scanf("%d %d",&x,&y);
			x--; y--;
			dsu(x,y);
		}
		else if(t==1)
		{
			int x,y;
			scanf("%d %d",&x,&y);
			x--; y--;
			swap(arr[x],arr[y]);
			x=dsu(x); y=dsu(y);
			if(x==y) continue;
			dsu.mod(x,arr[x],arr[y]);
			dsu.mod(y,arr[y],arr[x]);
		}
		else if(t==3)
		{
			//cout << bad << endl;
			printf("%s\n",(bad==0?"DA":"NE"));
		}
		else
		{
			printf("%lld\n",ans4);
		}
	}
}

Compilation message

zamjene.cpp: In function 'int main()':
zamjene.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
zamjene.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&arr[i]);
   ~~~~~^~~~~~~~~~~~~~
zamjene.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t);
   ~~~~~^~~~~~~~~
zamjene.cpp:105:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&x,&y);
    ~~~~~^~~~~~~~~~~~~~~
zamjene.cpp:112:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&x,&y);
    ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 8192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 8192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 8192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 8192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 8192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 8704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 92 ms 12024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1482 ms 50456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2503 ms 90092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1230 ms 51520 KB Output isn't correct
2 Halted 0 ms 0 KB -