oj.uz

답안 #567363

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
567363 2022-05-23T10:57:28 Z MilosMilutinovic 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++14
0 / 100
 13 ms 19028 KB 
#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()*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(u)!=in[v].end()) {
			in[v].erase(in[v].find(u));
		}
		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 u,v;
		scanf("%lld%lld",&u,&v);
		u=fa[u],v=fa[v];
		if (fa[u]!=fa[v]) {
			if (e[v].find(u)!=e[v].end()) {
				unite(u,v);
			} else {
				add(v,-1);
				in[v].insert(u);
				e[u].insert(v);
				r[v].insert(u);
				add(v,1);
			}
		}
		printf("%lld\n",ans);
	}
}

Compilation message

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",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 19012 KB Output is correct
2 Correct 13 ms 19028 KB Output is correct
3 Correct 13 ms 19028 KB Output is correct
4 Correct 13 ms 19000 KB Output is correct
5 Incorrect 10 ms 19028 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 19012 KB Output is correct
2 Correct 13 ms 19028 KB Output is correct
3 Correct 13 ms 19028 KB Output is correct
4 Correct 13 ms 19000 KB Output is correct
5 Incorrect 10 ms 19028 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 19012 KB Output is correct
2 Correct 13 ms 19028 KB Output is correct
3 Correct 13 ms 19028 KB Output is correct
4 Correct 13 ms 19000 KB Output is correct
5 Incorrect 10 ms 19028 KB Output isn't correct
6 Halted 0 ms 0 KB -