oj.uz

답안 #444078

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
444078 2021-07-13T05:35:27 Z kig9981 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 10 ms 14412 KB 
#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

set<pair<int,int>> adj[100000], radj[100000];
set<int> oadj[100000];
int color[100000], cnt[100000];
long long ans;

int find_(int a) {return color[a]=a==color[a] ? a:find_(color[a]);}

void erase_value(int a, int b, set<pair<int,int>> *adj)
{
	auto L=adj[a].lower_bound({b,0}), R=adj[a].upper_bound({b,0x7fffffff});
	while(L!=R) {
		auto temp=L++;
		adj[a].erase(temp);
	}
}

void replace_value(int c, int a, int b, set<pair<int,int>> *adj)
{
	auto L=adj[c].lower_bound({b,0}), R=adj[c].upper_bound({b,0x7fffffff});
	vector<pair<int,int>> T;
	while(L!=R) {
		auto temp=L++;
		T.emplace_back(a,temp->second);
		adj[c].erase(temp);
	}
	for(auto t: T) adj[c].insert(t);
}

void union_(int a, int b)
{
	a=find_(a); b=find_(b);
	if(a==b) return;
	if(adj[a].size()+radj[a].size()<adj[b].size()+radj[b].size()) swap(a,b);
	ans-=cnt[a]*(adj[a].size()+cnt[a]-1LL)+cnt[b]*(adj[b].size()+cnt[b]-1LL);
	color[b]=a;
	cnt[a]+=cnt[b];
	erase_value(a,b,adj); erase_value(b,a,adj);
	erase_value(a,b,radj); erase_value(b,a,radj);
	for(auto n: adj[b]) {
		replace_value(n.first,a,b,radj);
		adj[a].insert(n);
	}
	for(auto n: radj[b]) {
		replace_value(n.first,a,b,adj);
		radj[a].insert(n);
	}
	ans+=cnt[a]*(adj[a].size()+cnt[a]-1LL);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M;
	cin>>N>>M;
	for(int i=0;i<N;i++) cnt[color[i]=i]=1;
	while(M--) {
		int a, b, x, y;
		cin>>a>>b;
		oadj[--a].insert(--b);
		if((x=find_(a))==(y=find_(b)) || adj[y].find({x,a})!=adj[y].end()) {
			if(oadj[b].find(a)!=oadj[b].end()) union_(a,b);
			cout<<ans<<'\n';
			continue;
		}
		adj[y].emplace(x,a);
		radj[x].emplace(y,b);
		ans+=cnt[y];
		auto it=adj[x].lower_bound({y,0});
		if(oadj[b].find(a)!=oadj[b].end()) union_(a,b);
		cout<<ans<<'\n';
	}
	return 0;
}

Compilation message

joitter2.cpp: In function 'int main()':
joitter2.cpp:84:8: warning: variable 'it' set but not used [-Wunused-but-set-variable]
   84 |   auto it=adj[x].lower_bound({y,0});
      |        ^~

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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