Submission #532473

#	Time	Username	Problem	Language	Result	Execution time	Memory
532473		colazcy	Zamjene (COCI16_zamjene)	C++17	140 / 140	4178 ms	180628 KiB

zamjene

#include <cstdio>
#include <cassert>
#include <vector>
#include <random>
#include <chrono>
#include <set>
#include <map>
#include <algorithm>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ll = long long;
using ull = unsigned long long;
constexpr int maxn = 1e6 + 10;
	
ull trans[maxn];
int n,q,now[maxn],target[maxn];
std::mt19937_64 eng(743);
namespace dsu{
	int f[maxn],sz[maxn];
	void init(){
		rep(i,1,n)f[i] = i,sz[i] = 1;
	}
	int find(const int x){return x == f[x] ? x : f[x] = find(f[x]);}
};
std::map<ull,int> mp;
ll ans;
ull sum[maxn];
void ins(const ull s,const int sz){
	if(s != 0)ans += 1ll * sz * mp[-s];
	mp[s] += sz;
}
void del(const ull s,const int sz){
	mp[s] -= sz;
	if(s != 0)ans -= 1ll * sz * mp[-s];
}
void init(){
	rep(i,1,n)target[i] = now[i];
	std::sort(target + 1,target + 1 + n);
	rep(i,1,n)trans[now[i]] = eng();
	dsu::init();
	rep(i,1,n)
		sum[i] = trans[now[i]] - trans[target[i]];
	rep(i,1,n)ins(sum[i],1);
}

void modify_swap(const int a,const int b){
	let x = dsu::find(a),y = dsu::find(b);
	if(x == y){
		std::swap(now[a],now[b]);
		return;
	}
	del(sum[x],dsu::sz[x]);
	del(sum[y],dsu::sz[y]);
	sum[x] -= trans[now[a]];
	sum[y] -= trans[now[b]];
	std::swap(now[a],now[b]);
	sum[x] += trans[now[a]];
	sum[y] += trans[now[b]];
	ins(sum[x],dsu::sz[x]);
	ins(sum[y],dsu::sz[y]);
}
void modify_merge(const int a,const int b){
	let x = dsu::find(a),y = dsu::find(b);
	if(x == y)return;
	del(sum[x],dsu::sz[x]);
	del(sum[y],dsu::sz[y]);
	sum[y] += sum[x];
	dsu::sz[y] += dsu::sz[x];
	dsu::f[x] = y;
	ins(sum[y],dsu::sz[y]);
}
bool query_sort(){
	return mp[0] == n;
}
ll query_count(){
	return ans;
}
int main(){
	// std::freopen("zamjene.in","r",stdin);
	// std::freopen("zamjene.out","w",stdout);
	std::scanf("%d %d",&n,&q);
	rep(i,1,n)std::scanf("%d",now + i);
	init();
	repn(q){
		int opt,x,y; std::scanf("%d",&opt);
		if(opt == 1){
			std::scanf("%d %d",&x,&y);
			modify_swap(x,y);
		}else if(opt == 2){
			std::scanf("%d %d",&x,&y);
			modify_merge(x,y);
		}else if(opt == 3)std::puts(query_sort() ? "DA" : "NE");
		else if(opt == 4)std::printf("%lld\n",query_count());
	}	
	std::fclose(stdin);
	std::fclose(stdout);
	return 0;
}

Compilation message (stderr)

zamjene.cpp: In function 'int main()':
zamjene.cpp:85:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |  std::scanf("%d %d",&n,&q);
      |  ~~~~~~~~~~^~~~~~~~~~~~~~~
zamjene.cpp:86:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  rep(i,1,n)std::scanf("%d",now + i);
      |            ~~~~~~~~~~^~~~~~~~~~~~~~
zamjene.cpp:89:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   int opt,x,y; std::scanf("%d",&opt);
      |                ~~~~~~~~~~^~~~~~~~~~~
zamjene.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |    std::scanf("%d %d",&x,&y);
      |    ~~~~~~~~~~^~~~~~~~~~~~~~~
zamjene.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |    std::scanf("%d %d",&x,&y);
      |    ~~~~~~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14