#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define vi vector<int>
#define vpii vector<pii>
#define vp3i vector<p3i>
#define vpll vector<pll>
#define vp3l vector<p3l>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() ((rand() << 14)+rand())
#define scan(X) do{while((X=getchar())<'0'); for(X-='0'; '0'<=(_=getchar()); X=(X<<3)+(X<<1)+_-'0');}while(0)
char _;
#define pi 3.14159265358979323846
int n, m, x, y, c, c2;
vector<vector<int> > comp;
vector<int> curr;
vector<int> v[100005];
vector<int> w[200005];
int ord[100005], low[100005];
ll dp[2][200005];
vector<int> last;
bool crit[100005], current[100005];
ll ans;
void dfs2(int N, int P){
//dont count the articulation point twice
//counts all paths up to current component
//counts all paths at an articulation point below it that does not end on it
ll sz;
/*if (N <= 100000){
sz = comp[N].size();
}*/
dp[0][N] = 1;
fox(l, w[N].size()){
int nxt = w[N][l];
if (nxt == P) continue;
dfs2(nxt, N);
if (N > 100000 || 1){
//articulation
ans += dp[1][N]*dp[0][nxt] + dp[0][N]*dp[1][nxt];
dp[0][N] += dp[0][nxt];
dp[1][N] += dp[1][nxt];
dp[1][N] += dp[0][nxt];
} else {
//component
ans += dp[0][nxt]*(sz-1)*(sz-2);
ans += dp[1][nxt]*(sz-1);
ans += dp[0][nxt]*dp[1][N];
ans += dp[1][nxt]*dp[0][N];
dp[0][N] += dp[0][nxt];
dp[1][N] += dp[1][nxt];
dp[1][N] += dp[0][nxt] * (sz - 2);
}
}
/*if (N <= 100000){
ans += (sz)*(sz-1)*(sz-2)/2;
dp[0][N] += (sz-1);
dp[1][N] += (sz-1)*(sz-2);
}*/
//cout << N << ' ' << sz << ' ' << dp[0][N] << ' ' << dp[1][N] << ' ' << ans << endl;
}
bool spec;
void dfs(int N, int P){
if (ord[N]) return;
last.pb(N);
current[N] = 1;
low[N] = ord[N] = ++c;
fox(l, v[N].size()){
int nxt = v[N][l];
if (nxt == P) continue;
if (ord[nxt]){
low[N] = min(low[N], ord[nxt]);
continue;
}
dfs(nxt, N);
if (low[nxt] >= ord[N]){
int top = -1;
curr.clear();
while(1){
top = last.back();
curr.pb(top);
if (top == N) break;
last.pop_back();
}
comp.pb(curr);
//cout << "*" << N << ' ' << curr.size() << endl;
if (N == 1 && crit[N]) spec = 1;
crit[N] = 1;
}
low[N] = min(low[N], current[nxt]?ord[nxt]:low[nxt]);
}
current[N] = 0;
//cout << N << ' ' << ord[N] << ' ' << low[N] << endl;
}
int32_t main(){
scanf("%i%i", &n, &m);
fox(l, m){
scanf("%i%i", &x, &y);
//x=l+1;
//y=(l+1)%n+1;
w[x].pb(y);
w[y].pb(x);
}
/*dfs(1, -1);
//crit[1] = spec;
//fox1(l, n) if (crit[l]) c2++;
//printf("%i\n", c2);
//fox1(l, n) if (crit[l]) printf("%i ", l); printf("\n");
//return 0;
fox(l, comp.size()){
fox(l2, comp[l].size()){
//cout << comp[l][l2] << ' ';
if (crit[comp[l][l2]]){
//cout << l << ' ' << comp[l][l2] << endl;
w[l].pb(comp[l][l2] + 100000);
w[comp[l][l2]+100000].pb(l);
}
}
//cout << endl;
}*/
dfs2(1, -1);
//dfs2(100001, -1);
cout << ans*2;
return 0;
}
Compilation message
count_triplets.cpp: In function 'void dfs2(int, int)':
count_triplets.cpp:23:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fox(k, x) for (int k=0; k<x; ++k)
count_triplets.cpp:54:7:
fox(l, w[N].size()){
~~~~~~~~~~~~~~
count_triplets.cpp:54:3: note: in expansion of macro 'fox'
fox(l, w[N].size()){
^~~
count_triplets.cpp: In function 'void dfs(int, int)':
count_triplets.cpp:23:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fox(k, x) for (int k=0; k<x; ++k)
count_triplets.cpp:88:7:
fox(l, v[N].size()){
~~~~~~~~~~~~~~
count_triplets.cpp:88:3: note: in expansion of macro 'fox'
fox(l, v[N].size()){
^~~
count_triplets.cpp: In function 'int32_t main()':
count_triplets.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i%i", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
count_triplets.cpp:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i%i", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
977 ms |
1049600 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 |
Runtime error |
977 ms |
1049600 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 |
1095 ms |
297980 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 3 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 4 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 5 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 6 |
Correct |
9 ms |
7424 KB |
Output is correct |
| 7 |
Correct |
9 ms |
7424 KB |
Output is correct |
| 8 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 9 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 10 |
Incorrect |
8 ms |
7424 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
13176 KB |
Output is correct |
| 2 |
Correct |
120 ms |
13300 KB |
Output is correct |
| 3 |
Correct |
90 ms |
13304 KB |
Output is correct |
| 4 |
Correct |
98 ms |
13304 KB |
Output is correct |
| 5 |
Correct |
127 ms |
13244 KB |
Output is correct |
| 6 |
Correct |
94 ms |
17528 KB |
Output is correct |
| 7 |
Correct |
86 ms |
15992 KB |
Output is correct |
| 8 |
Correct |
86 ms |
15352 KB |
Output is correct |
| 9 |
Correct |
76 ms |
14584 KB |
Output is correct |
| 10 |
Incorrect |
66 ms |
13272 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 3 |
Runtime error |
841 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
13176 KB |
Output is correct |
| 2 |
Correct |
73 ms |
13208 KB |
Output is correct |
| 3 |
Execution timed out |
1052 ms |
1049600 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
977 ms |
1049600 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 |
Runtime error |
977 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
