#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<int, int> pii;
const ll MOD = 1e9 + 7;
//Making Friends on Joitter is Fun: JOI 2020/2
//Problem: https://oj.uz/problem/view/JOI20_joitter2
int n, m;
//set<int> conTo[100005]; //ConTo[a] contains things that connect to group a
set<int> conU[100005]; //conU[a] contains a cup conTo[a]
set<int> tGraph[100005]; // graph of arrows from pA to pB
set<int> bGraph[100005];
int cSize[100005];
int up[100005];
int sumT[100005]; //sumT[a] = sum of cSize[x] for x in conTo[a]
int curAns;
queue<pii> merg;
void goIn(int a, int b) {
tGraph[a].insert(b);
bGraph[b].insert(a);
if (tGraph[b].find(a) != tGraph[b].end()) merg.push({ a,b });
}
int par(int b) {
return (b == up[b] ? b : (up[b] = par(up[b])));
}
void con(int a, int 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 (int i : tGraph[b]) {
bGraph[i].erase(b);
goIn(a, i);
}
for (int i : bGraph[b]) {
tGraph[i].erase(b);
goIn(i, a);
}
}
void init() {
for (int 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 (int i = 0; i < m; ++i) {
int 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(a), par(b));
}
}
cout << curAns << endl;
}
return 0;
}
Compilation message
joitter2.cpp: In function 'int main()':
joitter2.cpp:92:9: warning: variable 'p' set but not used [-Wunused-but-set-variable]
92 | pii p = merg.front();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
14412 KB |
Output is correct |
| 2 |
Correct |
6 ms |
14412 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
14408 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
14412 KB |
Output is correct |
| 2 |
Correct |
6 ms |
14412 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
14408 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
14412 KB |
Output is correct |
| 2 |
Correct |
6 ms |
14412 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
14408 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
