Submission #211998

#	Time	Username	Problem	Language	Result	Execution time	Memory
211998		sealnot123	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	14 ms	19072 KiB

joitter2

#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()

using namespace std;

typedef pair<int,int> PII;
typedef long long LL;
typedef double DD;
typedef long double LD;
typedef pair<LL,LL> PLL;
typedef pair<DD,DD> PDD;
typedef vector<int> VI;
typedef vector<LL> VL;
const int N=100007;
LL ans = 0;

multiset<int> I[N], O[N];
multiset<int>::iterator it, it2;
set< PII > II[N], OO[N];
set< PII >::iterator iit, iit2;
int p[N], s[N];

int fin(int a){
	if(a == p[a]) return a;
	return p[a] = fin(p[a]);
}

set<int> wait;

LL val(int a){
	return (LL)s[a]*(s[a]-1) + (LL)SZ(I[a])*s[a];
}

void merge(int a, int b){
	/*printf("(%d,%d)\n",a,b);*/
	ans -= val(a)+val(b);
	/*printf("asdfdas %d\n",ans);*/
	I[a].erase(b); O[a].erase(b);
	I[b].erase(a); O[b].erase(a);
	if(SZ(I[a])+SZ(O[a])+SZ(II[a]) < SZ(I[b])+SZ(O[b])+SZ(OO[a])) swap(a,b);
	int i,j;
	for(it = I[b].begin(); it != I[b].end(); it++){
		it2 = O[a].find(*it);
		if(it2 != O[a].end()) wait.insert(*it);
		O[*it].insert(a);
		I[a].insert(*it);
	}
	for(it = I[b].begin(); it != I[b].end(); it++)
		O[*it].erase(b);

	for(it = O[b].begin(); it != O[b].end(); it++){
		it2 = I[a].find(*it);
		if(it2 != I[a].end()) wait.insert(*it);
		I[*it].insert(a);
		O[a].insert(*it);
	}
	for(it = O[b].begin(); it != O[b].end(); it++)
		I[*it].erase(b);

	for(PII e : II[b]){
		if(e.y == a){
			iit = OO[a].find(PII(e.x, b));
			OO[a].erase(iit);
			continue;
		}
		OO[e.y].insert(PII(e.x, a));
		iit = OO[e.y].find(PII(e.x, b));
		OO[e.y].erase(iit);
		II[a].insert(e);
	}
	//printf("jazco\n");
	for(PII e : OO[b]){
		if(e.y == a){
			iit = II[a].find(PII(e.x, b));
			II[a].erase(iit);
			continue;
		}
		II[e.y].insert(PII(e.x, a));
		iit = II[e.y].find(PII(e.x, b));
		II[e.y].erase(iit);
		OO[a].insert(e);
	}

	I[b].clear(); O[b].clear();
	II[b].clear(); OO[b].clear();

	/*printf("result %d(%d) :\n",a,s[a]+s[b]);
	printf("in : "); for(int e : I[a]) printf("%d ",e);
	printf("\nout : "); for(int e : O[a]) printf("%d ",e);
	printf("\n");*/
	p[b] = a;
	s[a] += s[b];
	ans += val(a);

	if(wait.empty()) return;
	int x = *wait.begin();
	wait.erase(wait.begin());
	merge(a, x);
}

int main(){
	int i,j,k,l,a,b,c,d;
	int n, m;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){
		s[i] = 1;
		p[i] = i;
	}
	while(m--){
		scanf("%d%d",&a,&b);
		c = a;
		a = fin(a); b = fin(b);
		if(a != b && OO[a].find(PII(c, b)) == OO[a].end()){
			it = I[a].find(b);
			if(it != I[a].end()){
					/*printf("must merge\n");*/
				merge(a, b);
			}else{
				O[a].insert(b);
				I[b].insert(a);
				OO[a].insert(PII(c, b));
				II[b].insert(PII(c, a));
				ans += s[b];
			}
		}
		/*printf("XXXXXXXXXXXXXXXXXXXx");*/
		printf("%lld\n",ans);
	}
	return 0;
}
/*
4 6
1 2
2 3
3 2
1 3
3 4
4 3

6 10
1 2
2 3
3 4
4 5
5 6
6 5
5 4
4 3
3 2
2 1

*/

Compilation message (stderr)

joitter2.cpp: In function 'void merge(int, int)':
joitter2.cpp:46:6: warning: unused variable 'i' [-Wunused-variable]
  int i,j;
      ^
joitter2.cpp:46:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;
        ^
joitter2.cpp: In function 'int main()':
joitter2.cpp:107:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
        ^
joitter2.cpp:107:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
          ^
joitter2.cpp:107:12: warning: unused variable 'l' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
            ^
joitter2.cpp:107:20: warning: unused variable 'd' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
                    ^
joitter2.cpp:109: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:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~

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