제출 #245411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
245411		TadijaSebez	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++11	0 / 100	10 ms	9600 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100050;
set<int> in[N],all[N];
int my[N];
ll ans;
ll Calc(int cmp){
	return (ll)all[cmp].size()*((int)all[cmp].size()-1)+(ll)in[cmp].size()*all[cmp].size();
}
void Del(int cmp){
	ans-=Calc(cmp);
}
void Add(int cmp){
	ans+=Calc(cmp);
}
int main(){
	int n,m;scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++)all[i].insert(i),my[i]=i;
	set<pair<int,int>> edg;
	for(int i=1;i<=m;i++){
		int u,v;scanf("%i %i",&u,&v);
		if(edg.count({v,u})){
			int A=my[u],B=my[v];
			Del(A);Del(B);
			if(all[A].size()+in[A].size()>all[B].size()+in[B].size())swap(A,B);
			for(int x:all[A]){
				if(in[B].count(x))in[B].erase(x);
				all[B].insert(x);
				my[x]=B;
			}
			all[A].clear();
			for(int x:in[A]){
				if(!all[B].count(x))in[B].insert(x);
			}
			in[A].clear();
			Add(B);
		}else{
			Del(my[v]);
			in[my[v]].insert(u);
			Add(my[v]);
		}
		edg.insert({u,v});
		printf("%lld\n",ans);
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

joitter2.cpp: In function 'int main()':
joitter2.cpp:18:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n,m;scanf("%i %i",&n,&m);
          ~~~~~^~~~~~~~~~~~~~~
joitter2.cpp:22:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u,v;scanf("%i %i",&u,&v);
           ~~~~~^~~~~~~~~~~~~~~

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