Submission #211825

#	Time	Username	Problem	Language	Result	Execution time	Memory
211825		arnold518	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	1519 ms	79616 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int MAXM = 3e5;

int N, M;

int par[MAXN+10], sz[MAXN+10];
set<int> in[MAXN+10], out[MAXN+10], point[MAXN+10], uf[MAXN+10];
ll ans;

int Find(int x) { return x==par[x] ? x : par[x]=Find(par[x]); }

void Union(int pu, int pv)
{
	if(in[pv].size()+out[pv].size()+point[pv].size()+uf[pv].size()>in[pu].size()+out[pu].size()+point[pu].size()+uf[pu].size()) swap(pu, pv);

	//printf("PU %d : ", pu); for(auto it : point[pu]) printf("%d ", it); printf("\n");
	//printf("PV %d : ", pv); for(auto it : point[pv]) printf("%d ", it); printf("\n");

	for(auto it : uf[pv]) if(!point[pu].count(it)) ans+=sz[pu];
	//for(auto it : uf[pu]) if(!point[pv].count(it)) ans+=sz[pv];

	//printf("HI %lld\n", ans);
	ans+=(ll)sz[pu]*sz[pv];
	for(auto it : point[pv]) if(uf[pu].count(it)) ans-=sz[pv];

	ll t=point[pu].size();
	for(auto it : uf[pv]) if(point[pu].count(it)) t--;
	for(auto it : point[pv]) if(point[pu].count(it)) t--;
	//printf("HI1 %lld\n", t);
	ans+=t*sz[pv];

	t=point[pv].size();
	for(auto it : point[pv]) if(uf[pu].count(it)) t--;
	for(auto it : point[pv]) if(point[pu].count(it)) t--;
	//printf("HI2 %lld\n", t);
	ans+=t*sz[pu];

	vector<pii> V;
	for(auto it : out[pv]) if(in[pu].count(it) && !in[pv].count(it)) V.push_back({it, pu});
	for(auto it : in[pv]) if(!in[pu].count(it) && out[pu].count(it)) V.push_back({it, pu});

	for(auto it : in[pv])
	{
		in[pu].insert(it);
		out[it].erase(pv);
		out[it].insert(pu);
	}
	for(auto it : out[pv])
	{
		out[pu].insert(it);
		in[it].erase(pv);
		in[it].insert(pu);
	}

	for(auto it : uf[pv]) uf[pu].insert(it), point[pu].erase(it);
	for(auto it : point[pv]) if(!uf[pu].count(it)) point[pu].insert(it);

	par[pv]=pu; sz[pu]+=sz[pv];
	in[pv].clear(); out[pv].clear();
	//in[pu].erase(pv); out[pu].erase(pv);

	for(auto it : V) if(out[it.second].count(it.first)) Union(it.first, it.second);
}

int main()
{
	int i, j;

	scanf("%d%d", &N, &M);

	for(i=1; i<=N; i++) par[i]=i, sz[i]=1, uf[i].insert(i);
	for(i=1; i<=M; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);

		int pu=Find(u), pv=Find(v);

		if(pu!=pv && !point[pv].count(u))
		{
			out[pu].insert(pv);
			in[pv].insert(pu);
			point[pv].insert(u);
			ans+=sz[pv];

			if(out[pv].count(pu)) Union(pu, pv);
		}
		//for(j=1; j<=N; j++) printf("%d ", par[j]); printf("\n");
		printf("%lld\n", ans);
	}
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:74:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
joitter2.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
joitter2.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 16 / 16
• Subtask 3: 83 / 83