Submission #567373

#	Time	Username	Problem	Language	Result	Execution time	Memory
567373		MilosMilutinovic	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	967 ms	75352 KiB

joitter2

#include<bits/stdc++.h>
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
#define fi first
#define se second
#define PB push_back
#define uint unsigned
#define int long long
using namespace std;
const int N=100050;
int n,m,fa[N];
set<int> ch[N],e[N],r[N],in[N];
ll ans;
ll calc(int x){
	return ch[x].size()*1LL*(ch[x].size()-1)+in[x].size()*1LL*ch[x].size();
}
void add(int x,int c){ ans+=(calc(x)*c); }
int SZ(int x){ return ch[x].size()+e[x].size()+r[x].size()+in[x].size(); }
int unite(int u,int v){
	if (ch[u].empty()) return v;
	if (ch[v].empty()) return u;
	add(u,-1); add(v,-1);
	e[v].erase(e[v].find(u));
	r[u].erase(r[u].find(v));
	if (SZ(u)>SZ(v)) swap(u,v);
	for (int x:ch[u]) {
		if (in[v].find(x)!=in[v].end()) {
			in[v].erase(in[v].find(x));
		}
		ch[v].insert(x);
		fa[x]=v;
	}
	ch[u].clear();
	for (int x:in[u]) {
		if (ch[v].find(x)==ch[v].end()) {
			in[v].insert(x);
		}
	}
	in[u].clear();
	vector<int> adj;
	for (int x:e[u]) {
		if (r[v].find(x)!=r[v].end()) {
			adj.PB(x);
		}
		r[x].erase(r[x].find(u));
		if (e[v].find(x)==e[v].end()) {
			e[v].insert(x);
			r[x].insert(v);
		}
	}
	e[u].clear();
	for (int x:r[u]) {
		if (e[v].find(x)!=e[v].end()) {
			adj.PB(x);
		}
		e[x].erase(e[x].find(u));
		if (r[v].find(x)==r[v].end()) {
			r[v].insert(x);
			e[x].insert(v);
		}
	}
	r[u].clear();
	add(v,1);
	sort(adj.begin(),adj.end());
	adj.erase(unique(adj.begin(),adj.end()),adj.end());
	for (int x:adj) if (v!=x) v=unite(v,x);
	return v;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	For(i,1,n){
		ch[i].insert(i);
		fa[i]=i;
	}
	while(m--) {
		int a,b;
		scanf("%lld%lld",&a,&b);
		int u=fa[a],v=fa[b];
		if (u!=v) {
			if (e[v].find(u)!=e[v].end()) {
				unite(u,v);
			} else {
				add(v,-1);
				in[v].insert(a);
				e[u].insert(v);
				r[v].insert(u);
				add(v,1);
			}
		}
		printf("%lld\n",ans);
	}
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  scanf("%lld%lld",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
joitter2.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |   scanf("%lld%lld",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

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