#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
const double PI = 4 * atan(1);
#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define vpd vector<pair<double, double>>
#define pd pair<double, double>
#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)
#define trav(a, x) for (auto& a : x)
void fast_io(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
}
void io(string taskname){
string fin = taskname + ".in";
string fout = taskname + ".out";
const char* FIN = fin.c_str();
const char* FOUT = fout.c_str();
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
fast_io();
}
const int MAX = 1e5 + 5;
vi adj[MAX];
vi tree[MAX];
vi comp[MAX];
vi bcomp[MAX];
int sub[MAX];
int parent[MAX];
int dfs(int src, int par){
parent[src] = par;
sub[src] = sz(bcomp[src]);
for(int nxt: tree[src]){
if(nxt != par){
sub[src] += dfs(nxt, src);
}
}
sub[src] -= (sz(tree[src]) - (par==-1? 0: 1));///subtract out the the others, but include the parent
return sub[src];
}
template<int SZ> struct BCC {
int N;
vi adj[SZ];
vector<vpi> fin;
void addEdge(int u, int v) { adj[u].pb(v), adj[v].pb(u); }
int ti = 0, disc[SZ], low[SZ], comp[SZ], par[SZ];
vpi st;
void BCCutil(int u, bool root = 0) {
disc[u] = low[u] = ti++;
int child = 0;
trav(i,adj[u]) if (i != par[u])
if (disc[i] == -1) {
child ++; par[i] = u;
st.pb({u,i});
BCCutil(i);
low[u] = min(low[u],low[i]);
// disc[u] < low[i]: bridge
if ((root && child > 1) || (!root && disc[u] <= low[i])) { // articulation point!
vpi tmp;
while (st.back() != mp(u,i)) tmp.pb(st.back()), st.pop_back();
tmp.pb(st.back()), st.pop_back();
fin.pb(tmp);
}
} else if (disc[i] < disc[u]) {
low[u] = min(low[u],disc[i]);
st.pb({u,i});
}
}
void bcc(int _N) {
N = _N;
f1r(i,1,N+1) par[i] = disc[i] = low[i] = -1;
f1r(i,1,N+1) if (disc[i] == -1) {
BCCutil(i,1);
if (sz(st)) fin.pb(st);
st.clear();
}
}
};
BCC<MAX> bcc;
bool contains(int i, int x){
int l = 0;
int r = sz(bcomp[i]) - 1;
while(l<= r){
int m = (l+r)/2;
if(bcomp[i][m] == x) return true;
else if(bcomp[i][m]<x) l = m+1;
else r = m-1;
}
return false;
}
int main(){
fast_io();
int n, m;
cin >> n >> m;
f0r(i, m){
int u, v;
cin >> u >> v;
u--;
v--;
adj[u].eb(v);
adj[v].eb(u);
bcc.addEdge(u+1, v+1);
}
bcc.bcc(n);
int sz = sz(bcc.fin);
f0r(i, sz){
// cout << i <<" : ";
for(auto e: bcc.fin[i]){
comp[e.f-1].eb(i);
comp[e.s-1].eb(i);
bcomp[i].eb(e.f-1);
bcomp[i].eb(e.s-1);
// cout << "(" << e.f-1<< ", " << e.s-1<< ")" << " ";
}
// cout << endl;
}
f0r(i, n){
set<int> s (all(comp[i]));
comp[i].assign(all(s));
}
f0r(i, sz){
set<int> s (all(bcomp[i]));
bcomp[i].assign(all(s));
}
f0r(i,sz){
for(int x: bcomp[i]){
for(int nxt: comp[x]){
if(nxt == i) continue;
tree[i].eb(nxt);
}
}
}
dfs(0, -1);
ll ans = 0;
f0r(i, n){
ll cur = n-1;
cur = cur*(cur-1);
for(int c: comp[i]){
for(int nxt: tree[c]){
if(contains(nxt, i)){
continue;
}
if(nxt == parent[c]){
ll subtract = n - sub[c] + 1;
//if(i == 0) cout << subtract<< " subtract " << sub[nxt] << " " << nxt << endl;
subtract *= (subtract - 1);
cur -= subtract;
}
else{
ll subtract = (sub[nxt]);
subtract *= (subtract-1);
cur -= subtract;
}
}
}
// cout << i << " cur " << cur << endl;
ans += cur;
}
cout << ans << endl;
return 0;
}
Compilation message
count_triplets.cpp:1:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/stack:200000000")
count_triplets.cpp: In member function 'void BCC<SZ>::BCCutil(int, bool)':
count_triplets.cpp:81:27: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
trav(i,adj[u]) if (i != par[u])
^
count_triplets.cpp: In function 'void io(std::__cxx11::string)':
count_triplets.cpp:45:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(FIN, "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(FOUT, "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
12024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
12024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
240 ms |
38380 KB |
Output is correct |
| 2 |
Correct |
256 ms |
38376 KB |
Output is correct |
| 3 |
Incorrect |
252 ms |
34832 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1022 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1109 ms |
1048580 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1039 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1136 ms |
875236 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
12024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
12024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
