oj.uz

Submission #212000

# Submission time Handle Problem Language Result Execution time Memory
212000 2020-03-21T23:02:37 Z sealnot123 Making Friends on Joitter is Fun (JOI20_joitter2) C++14
0 / 100
 10 ms 9728 KB 
#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;

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(II[a])*s[a];
}

void merge(int a, int b){
	/*printf("kurwa\n");*/
	/*printf("(%d,%d)\n",a,b);*/
	ans -= val(a)+val(b);
	/*printf("asdfdas %d\n",ans);*/
	if(SZ(II[a])+SZ(OO[a]) < SZ(OO[b])+SZ(II[b])) swap(a,b);

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

	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(b, c)) == OO[a].end()){
			iit = II[a].lower_bound(PII(b, 0));
			if(iit != II[a].end() && iit->x == b){
					/*printf("must merge\n");*/
				merge(a, b);
			}else{
				OO[a].insert(PII(b, c));
				II[b].insert(PII(a, c));
				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

joitter2.cpp: In function 'int main()':
joitter2.cpp:93:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
        ^
joitter2.cpp:93:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
          ^
joitter2.cpp:93:12: warning: unused variable 'l' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
            ^
joitter2.cpp:93:20: warning: unused variable 'd' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
                    ^
joitter2.cpp:95: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:101: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.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 9 ms 9728 KB Output is correct
5 Incorrect 10 ms 9728 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 9 ms 9728 KB Output is correct
5 Incorrect 10 ms 9728 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 9 ms 9728 KB Output is correct
5 Incorrect 10 ms 9728 KB Output isn't correct
6 Halted 0 ms 0 KB -