Submission #474175

#	Time	Username	Problem	Language	Result	Execution time	Memory
474175		keta_tsimakuridze	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	13 ms	23676 KiB

joitter2

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t,n,q,par[N],cnt[N],sz[N], ans = 0;
map<int,int> follows[N], part[N];
vector<pair<int,pii> > edges[N];
int parent(int u) {
	return par[u] == u ? u : par[u] = parent(par[u]);
}
void merge(int u,int v) {
	u = parent(u), v = parent(v);
	if(edges[u].size() < edges[v].size()) swap(u,v);
	ans -= cnt[u] * sz[u]; 
	ans -= sz[v] * cnt[v];
	cnt[u] += cnt[v];
	for(int i = 0; i < edges[v].size(); i++) {
		int F = 0;
		int type = edges[v][i].f, a = edges[v][i].s.s, b = edges[v][i].s.f;
		if(type == 1) { 
			if(parent(a) == u || part[a][u]) F = 1,cnt[u]--;
			follows[parent(a)][u] = 1;
			part[a][u] = 1;
		}
		else {
			if(parent(a) == u) F = 1,cnt[u]--;
			follows[u][parent(a)] = 1;
			part[b][parent(a)] = 1;
		}
		if(!F) edges[u].push_back(edges[v][i]);
	}
	ans += sz[u] * sz[v] * 2 + cnt[u] * (sz[u] + sz[v]);
	par[v] = u;
	sz[u] += sz[v];
}
main(){
	cin >> n >> q;
	for(int i = 1; i <= n; i++) {
		par[i] = i;
		sz[i] = 1;
	}
	while(q--) {
		int u,v;
		cin >> u >> v;
		if(parent(u) == parent(v) || part[u][parent(v)]) {
			cout << ans <<"\n";
			continue;
		}		
		if(follows[parent(v)][parent(u)]) {
			merge(u,v);
		}
		else if(!part[u][parent(v)]){
			follows[parent(u)][parent(v)] = 1;
			part[u][parent(v)] = 1;
			edges[parent(u)].push_back({0,{u,v}});
			edges[parent(v)].push_back({1,{v,u}});
			ans += sz[parent(v)];
			cnt[parent(v)]++;
		}
		cout << ans << endl;
	}
	
 }

Compilation message (stderr)

joitter2.cpp: In function 'void merge(long long int, long long int)':
joitter2.cpp:20:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i = 0; i < edges[v].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~
joitter2.cpp: At global scope:
joitter2.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 | main(){
      | ^~~~

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