//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define trav(x,a) for (const auto& x: a)
#define sz(x) (int)(x).size()
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int _i = 1; _i <= (n); _i++) ni(a[_i])
#define nal(a, n) for (int _i = 1; _i <= (n); _i++) nl(a[_i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
const int N = 1e6 + 5;
const double eps = 1e-9;
int par[N];
set<int> eIn[N], eOut[N], comp[N];
ll ans, sz[N];
int qry(int x) { return x == par[x] ? x : par[x] = qry(par[x]); }
void upd(int u, int f) { ans += f * sz[u] * 1ll * (sz(comp[u]) - 1); }
deque<pii> pq;
void join(int u, int v) {
if (u == v) return;
{
if (eIn[u].count(v))
eIn[u].erase(eIn[u].find(v));
if (eIn[v].count(u))
eIn[v].erase(eIn[v].find(u));
if (eOut[u].count(v))
eOut[u].erase(eOut[u].find(v));
if (eOut[v].count(u))
eOut[v].erase(eOut[v].find(u));
}
if (sz(comp[u]) > sz(comp[v]))
swap(u, v);
par[u] = v;
sz[v] += sz[u];
trav(x, comp[u]) comp[v].insert(x);
trav(x, eIn[u]) {
if (eOut[v].count(x))
pq.pb({x, v});
eOut[x].erase(eOut[x].find(u));
eOut[x].insert(v);
eIn[v].insert(x);
}
trav(x, eOut[u]) {
if (eIn[v].count(x))
pq.pb({x, v});
eIn[x].erase(eIn[x].find(u));
eIn[x].insert(v);
eOut[v].insert(x);
}
eIn[u].clear();
eOut[u].clear();
comp[u].clear();
}
int main() {
int n, m; scanf("%d %d", &n, &m);
iota(par, par+n+1, 0);
fill(sz, sz+n+1, 1);
for (int i = 1; i <= n ; i++)
comp[i].insert(i);
while (m--) {
int u, v; scanf("%d %d", &u, &v);
if (eOut[qry(v)].count(qry(u))) {
pq.pb({u, v});
while (!pq.empty()) {
tie(u, v) = pq.front();
pq.pop_front();
upd(qry(u), -1);
upd(qry(v), -1);
join(qry(u), qry(v));
upd(qry(u), 1);
}
} else {
upd(qry(v), -1);
comp[qry(v)].insert(u);
eIn[qry(v)].insert(qry(u));
eOut[qry(u)].insert(qry(v));
upd(qry(v), 1);
}
printf("%lld\n", ans);
}
return 0;
}
Compilation message
joitter2.cpp: In function 'int main()':
joitter2.cpp:83:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n, m; scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
joitter2.cpp:89:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int u, v; scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
141304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
141304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
141304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
