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 <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll MOD = 1e9 + 7;
//Making Friends on Joitter is Fun: JOI 2020/2
//Problem: https://oj.uz/problem/view/JOI20_joitter2
ll n, m;
//set<ll> conTo[100005]; //ConTo[a] contains things that connect to group a
set<ll> conU[100005]; //conU[a] contains a cup conTo[a]
set<ll> tGraph[100005]; // graph of arrows from pA to pB
set<ll> bGraph[100005];
ll cSize[100005];
ll up[100005];
ll sumT[100005]; //sumT[a] = sum of cSize[x] for x in conTo[a]
ll curAns;
queue<pii> merg;
void goIn(ll a, ll b) {
tGraph[a].insert(b);
bGraph[b].insert(a);
if (tGraph[b].find(a) != tGraph[b].end()) merg.push({ a,b });
}
ll par(ll b) {
return (b == up[b] ? b : (up[b] = par(up[b])));
}
void con(ll a, ll b) {//connects a to b
if (a == b) return;
curAns += conU[a].size() * cSize[b];
curAns += conU[b].size() * cSize[a];
if (conU[a].size() < conU[b].size()) swap(a, b);
for (auto itr = conU[b].begin(); itr != conU[b].end(); ++itr) {
if (conU[a].find(*itr) != conU[a].end()) curAns -= (cSize[a] + cSize[b]);
}
for (auto itr = conU[b].begin(); itr != conU[b].end(); ++itr) {
conU[a].insert(*itr);
}
up[b] = a;
cSize[a] += cSize[b];
tGraph[a].erase(b);
tGraph[b].erase(a);
bGraph[a].erase(b);
bGraph[b].erase(a);
for (ll i : tGraph[b]) {
bGraph[i].erase(b);
goIn(a, i);
}
for (ll i : bGraph[b]) {
tGraph[i].erase(b);
goIn(i, a);
}
}
void init() {
for (ll i = 1; i <= n; ++i) {
cSize[i] = 1;
up[i] = i;
conU[i].insert(i);
}
curAns = 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
init();
for (ll i = 0; i < m; ++i) {
ll a, b;
cin >> a >> b;
b = par(b);
if (par(a) != b && conU[b].find(a) == conU[b].end()) {
conU[b].insert(a);
curAns += cSize[b];
a = par(a);
goIn(a, b);
while (!merg.empty()) {
pii p = merg.front();
merg.pop();
con(par(p.first), par(p.second));
}
}
cout << curAns << endl;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |