# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
377181 | nafis_shifat | Making Friends on Joitter is Fun (JOI20_joitter2) | C++14 | 1635 ms | 125812 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
const int mxn=1e5+5;
const int inf=1e9;
int parent[mxn];
int sz[mxn];
set<int> adj[mxn];
set<int> in[mxn];
vector<int> nodes[mxn];
int sz2[mxn][2];
set<int> eds[mxn][2];
set<int> reps[mxn];
set<int> ireps[mxn];
ll ans = 0;
int findrep(int u) {
return parent[u] == u ? u : parent[u] = findrep(parent[u]);
}
void unite(int u,int v) {
int U = findrep(u);
int V = findrep(v);
if(U == V) return;
if(adj[V].count(U)) {
ans += 2 * sz[U] * sz[V];
if(sz[U] + sz2[U][0] + sz2[U][1] > sz[V] + sz2[V][0] + sz2[V][1]) swap(U,V);
vector<int> nod1,nod2;
for(int i : nodes[U]) {
auto it1 = eds[i][0].begin();
while(it1 != eds[i][0].end()) {
int x = *it1;
int X = findrep(x);
if(X == V) {
ans -= sz[V];
in[V].erase(U);
adj[U].erase(V);
eds[x][1].erase(i);
sz2[X][1]--;
it1 = eds[i][0].erase(it1);
sz2[U][0]--;
} else if(in[V].count(X)) {
nod1.push_back(X);
in[X].erase(U);
eds[x][1].erase(i);
sz2[X][1]--;
ans -= sz[X];
it1 = eds[i][0].erase(it1);
sz2[U][0]--;
} else it1++;
}
auto it2 = eds[i][1].begin();
while(it2 != eds[i][1].end()) {
int x = *it2;
int X = findrep(x);
if(X == V) {
ans -= sz[U];
adj[V].erase(U);
in[U].erase(V);
eds[x][0].erase(i);
sz2[X][0]--;
it2 = eds[i][1].erase(it2);
sz2[U][1]--;
} else if(adj[V].count(X)) {
nod2.push_back(X);
adj[X].erase(U);
eds[x][0].erase(i);
sz2[X][0]--;
ans -= sz[U];
it2 = eds[i][1].erase(it2);
sz2[U][1]--;
} else if(ireps[V].count(x)) {
sz2[U][1]--;
reps[x].erase(U);
eds[x][0].erase(i);
sz2[X][0]--;
it2 = eds[i][1].erase(it2);
ans -= sz[U];
} else it2++;
}
}
while(!ireps[U].empty()) {
auto it = ireps[U].begin();
ireps[V].insert(*it);
reps[*it].erase(U);
reps[*it].insert(V);
ireps[U].erase(it);
}
ans += sz2[U][1] * sz[V];
ans += sz2[V][1] * sz[U];
parent[U] = V;
sz[V] += sz[U];
sz2[V][0] += sz2[U][0];
sz2[V][1] += sz2[U][1];
while(!nodes[U].empty()) {
int x = nodes[U].back();
nodes[U].pop_back();
nodes[V].push_back(x);
}
while(!adj[U].empty()) {
int x = *adj[U].begin();
in[x].erase(U);
adj[U].erase(x);
adj[V].insert(x);
in[x].insert(V);
}
while(!in[U].empty()) {
int x = *in[U].begin();
in[U].erase(x);
adj[x].erase(U);
in[V].insert(x);
adj[x].insert(V);
}
for(int x : nod1) {
unite(V,x);
}
for(int x : nod2) {
unite(x,V);
}
} else {
if(reps[u].count(V)) return;
ans += sz[V];
eds[u][0].insert(v);
eds[v][1].insert(u);
adj[U].insert(V);
in[V].insert(U);
reps[u].insert(V);
ireps[V].insert(u);
sz2[U][0]++;
sz2[V][1]++;
}
}
int main() {
int n,m;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
parent[i] = i;
sz[i] = 1;
sz2[i][0] = sz2[i][1] = 0;
nodes[i].push_back(i);
}
for(int i = 1; i <= m; i++) {
int u,v;
scanf("%d%d",&u,&v);
unite(u,v);
cout<<ans<<endl;
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |