/*
/+==================================================+\
//+--------------------------------------------------+\\
|.|\\...>>>>>>> Hollwo_Pelw(ass) 's code <<<<<<<...//|.|
\\+--------------------------------------------------+//
\+==================================================+/
*/
#include <bits/stdc++.h>
using namespace std;
// type
typedef long long ll;
typedef long double ld;
// pair
#define F first
#define S second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<ld, ld>
// vector & !!?(string)
#define eb emplace_back
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) a.size()
#define len(a) a.length()
// I/O
#define open(file, in, out) if (fopen(file in, "r")) { \
freopen(file in, "r", stdin); \
freopen(file out, "w", stdout); \
}
#define FAST_IO std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define setpre(n) fixed << setprecision(n)
bool endline = false;
template<class T>
istream& operator >> (istream& inp, vector<T>& v){
for (auto& it : v) inp >> it;
return inp;
}
template<class T>
ostream& operator << (ostream& out, vector<T>& v){
for (auto& it : v) out << it << (endline ? "\n" : " ");
return out;
}
template<class T, class U>
istream& operator >> (istream& inp, pair<T, U>& v){
inp >> v.F >> v.S;
return inp;
}
template<class T, class U>
ostream& operator << (ostream& out, pair<T, U>& v){
out << v.F << ' ' << v.S;
return out;
}
#define debug(x) cout << #x << " : " << endl << x << endl;
#define Ptest(x) return cout << x << endl, (void) 0;
// geometry calculate
#define pi acos(-1.0)
#define g_sin(a) sin(a*pi/180)
#define g_cos(a) cos(a*pi/180)
#define g_tan(a) tan(a*pi/180)
// set val
#define ms0(a) memset(a, 0, sizeof(a));
#define ms1(a) memset(a, 1, sizeof(a));
#define msn1(a) memset(a, -1, sizeof(a));
#define msinf(a) memset(a, 0x3f3f3f, sizeof(a));
// constant
const int mod1 = 998244353, mod = 1e9 + 7;
const int MAXN = 1e5 + 5 , MAXM = 3e5 + 5;
const int inf = 2e9; const ll linf = 1e18;
// code
#define left node << 1, tl, tm
#define right node << 1 | 1, tm + 1, tr
// #define int long long
int n, m, par[MAXN];
ll ans, sz[MAXN];
set<int> adj[MAXN], radj[MAXN], fol[MAXN];
queue<pii> to_merge;
void weakedge(int u, int v){
adj[u].insert(v);
radj[v].insert(u);
// if now strong
if (adj[v].count(u))
to_merge.push({u, v});
}
int find(int u){
return par[u] = (par[u] == u ? u : par[u]);
}
int dsize(int u){
return fol[u].size() + radj[u].size() + adj[u].size();
}
void merge(int u, int v){
if (u == v) return ;
if (dsize(u) < dsize(v))
swap(u, v);
ans += sz[u] * fol[v].size() + sz[v] * fol[u].size();
par[v] = u;
sz[u] += sz[v];
for (auto f : fol[v]){
if (fol[u].count(f))
ans -= sz[u];
else
fol[u].insert(f);
}
adj[u].erase(v), radj[v].erase(u);
adj[v].erase(u), radj[u].erase(v);
for (auto f : adj[v]){
radj[f].erase(v);
weakedge(u, f);
}
for (auto f : radj[v]){
adj[f].erase(u);
weakedge(f, u);
}
}
void Solve(){
cin >> n >> m;
for (int i = 1; i <= n; i++){
par[i] = i;
sz[i] = 1;
fol[i].insert(i);
}
while(m --){
int u, v;
cin >> u >> v;
int pu = u, pv = v;
if (pu != pv && !fol[pv].count(u)){
fol[pv].insert(u);
ans += sz[pv];
weakedge(pu, pv);
while(!to_merge.empty()){
auto[uu, vv] = to_merge.front();
to_merge.pop();
merge(uu, vv);
// cout << "MERGE " << uu << ' ' << vv << endl;
}
}
cout << ans << "\n";
}
}
signed main(){
open("", ".inp", ".out");
FAST_IO; int TC = 1;
//cin >> TC;
while(TC--) Solve();
return 0;
}
/*
./-=====>>><<<-------- DEBUG -------->>><<<=====-\.
/.................................................\
+====================== INP ======================+
+====================== OUT ======================+
\................................................./
.\-=====>>><<<--------= END =-------->>><<<=====-/.
*/
Compilation message
joitter2.cpp: In function 'int main()':
joitter2.cpp:28:40: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
28 | freopen(file in, "r", stdin); \
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
joitter2.cpp:147:5: note: in expansion of macro 'open'
147 | open("", ".inp", ".out");
| ^~~~
joitter2.cpp:29:40: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
29 | freopen(file out, "w", stdout); \
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp:147:5: note: in expansion of macro 'open'
147 | open("", ".inp", ".out");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
14444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
14444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
14444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
