#include <bits/stdc++.h>
#define all(dataStructure) dataStructure.begin(),dataStructure.end()
#define ll long long
using namespace std;
namespace std {
template <typename T, int D>
struct _vector : public vector <_vector <T, D - 1>> {
static_assert(D >= 1, "Dimension must be positive!");
template <typename... Args>
_vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
};
// _vector <int, 3> a(n, m, k);: int a[n][m][k].
// _vector <int, 3> a(n, m, k, x);: int a[n][m][k] initialized with x.
template <typename T>
struct _vector <T, 1> : public vector <T> {
_vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
};
}
const int MAX = 1e5 + 3;
const ll MOD[] = {1000000007, 998244353};
int n, m;
int pa[MAX], sz[MAX];
set <int> followers[MAX], in[MAX], out[MAX];
vector <pair <int, int>> toJoin;
ll ans;
uint32_t getSize(int i) {
return followers[i].size() + in[i].size() + out[i].size();
}
void insertOneWay(int u, int v) {
out[u].insert(v);
in[v].insert(u);
if (out[v].count(u)) {
toJoin.push_back({u, v});
}
}
int findpa(int u) {
return u == pa[u] ? u : pa[u] = findpa(pa[u]);
}
void join(int u, int v) {
u = findpa(u);
v = findpa(v);
if (u == v) return;
if (getSize(u) < getSize(v)) swap(u, v);
ans += 1ll * sz[u] * followers[v].size() + 1ll * sz[v] * followers[u].size();
pa[v] = u;
sz[u] += sz[v];
for (int i : followers[v]) {
if (followers[u].count(i)) ans -= sz[u];
else followers[u].insert(i);
}
in[u].erase(v);
in[v].erase(u);
out[u].erase(v);
out[v].erase(u);
for (int i : in[v]) {
out[i].erase(v);
insertOneWay(i, u);
}
for (int i : out[v]) {
in[i].erase(v);
insertOneWay(u, i);
}
}
void Solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
pa[i] = i;
sz[i] = 1;
followers[i].insert(i);
}
int u, v;
while (m--) {
cin >> u >> v;
v = findpa(v);
if (findpa(u) != v && !followers[v].count(u)) {
followers[v].insert(u);
ans += sz[v];
u = findpa(u);
insertOneWay(u, v);
while (toJoin.size()) {
join(toJoin.back().first, toJoin.back().second);
toJoin.pop_back();
}
}
cout << ans << '\n';
}
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define TASK ""
if (fopen(TASK".INP", "r")) {
freopen(TASK".INP", "r", stdin);
freopen(TASK".OUT", "w", stdout);
}
if (fopen("TASK.INP", "r")) {
freopen("TASK.INP", "r", stdin);
freopen("TASK.OUT", "w", stdout);
}
/* int TEST = 1; cin >> TEST; while (TEST--) */ Solve();
cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
return 0;
}
Compilation message
joitter2.cpp: In function 'int32_t main()':
joitter2.cpp:109:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
109 | freopen(TASK".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp:110:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
110 | freopen(TASK".OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp:114:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | freopen("TASK.INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp:115:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
115 | freopen("TASK.OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14928 KB |
Output is correct |
| 2 |
Correct |
3 ms |
15096 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
14928 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14928 KB |
Output is correct |
| 2 |
Correct |
3 ms |
15096 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
14928 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14928 KB |
Output is correct |
| 2 |
Correct |
3 ms |
15096 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
14928 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
