#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<int>> graph;
vector<vector<int>> cgraph;
vector<int> comp;
vector<int> art;
vector<int> low;
vector<int> num;
vector<int> vis;
stack<int> s;
int c = 0;
int d = 0;
int root = 0;
int sub = 0;
vector<ll> compsize;
ll sol = 0;
int n, m;
int N = 1e6;
void dfs(int i, int p)
{
num[i] = low[i] = ++c;
s.push(i);
for (int ele:graph[i])
{
if (ele == p) continue;
if (!num[ele])
{
if (i == root) sub++;
dfs(ele, i);
if (low[ele]>=num[i]) art[i] = 1;
if (low[ele]==num[i])
{
while(s.top() != i)
{
comp[s.top()] = d;
compsize[d]++;
s.pop();
}
comp[i] = d;
compsize[d]++;
s.pop();
d++;
}
low[i] = min(low[i], low[ele]);
}
else low[i] = min(low[i], num[ele]);
}
if (num[i]==low[i] && comp[i]==-1)
{
art[i] = 1;
while (s.top() != i)
{
comp[s.top()] = d;
compsize[d]++;
s.pop();
}
comp[i] = d;
compsize[d]++;
s.pop();
d++;
}
}
int dfs2(int i, int p)
{
vis[i] = 1;
ll ss = 0;
vector<int> cs;
vector<int> v;
for (int ele:cgraph[i])
{
if (!vis[ele])
{
if (ele < N) cs.push_back(compsize[ele]);
int h = dfs2(ele, i);
ss += h;
v.push_back(h);
}
}
if (i >= N) ss++;
else ss+=compsize[i];
ss-=v.size();
if (p != -1)
{
if (p < N) cs.push_back(compsize[p]);
v.push_back(sub-ss);
}
if (i >= N)
{
for (int ele:v)
{
sol += (ele-1)*(sub-ele);
}
}
else
{
int css = compsize[i]-v.size();
sol += (compsize[i]-1)*(compsize[i]-2)*(compsize[i]);
for (ll ele:v)
{
sol += ele*(sub-ele-1)*(compsize[i]);
}
}
return ss;
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin >> n >> m;
graph.assign(n, vector<int>());
cgraph.assign(2*N, vector<int>());
compsize.assign(n, 0);
low.assign(n, 0);
num.assign(n, 0);
comp.assign(n, -1);
art.assign(n, 0);
vis.assign(2*N, 0);
for (int i =0; i < m; i++)
{
int a, b;
cin >> a >> b;
a--; b--;
graph[a].push_back(b);
graph[b].push_back(a);
}
vector<int> subtree(n, 0);
for (int i = 0; i < n; i++)
{
if (!num[i])
{
root = i;
sub = 0;
c = 0;
dfs(i, -1);
subtree[i] = c;
if (sub==1) art[i] = 0;
}
}
d = N;
for (int i = 0; i <n; i++)
{
if (art[i])
{
for (int ele:graph[i])
{
cgraph[d].push_back(comp[ele]);
cgraph[comp[ele]].push_back(d);
}
comp[i] = d;
d++;
}
}
for (int i = 0; i < n; i++)
{
if (!vis[comp[i]])
{
sub = subtree[i];
dfs2(comp[i], -1);
}
}
cout << sol << "\n";
return 0;
}
Compilation message
count_triplets.cpp: In function 'int dfs2(int, int)':
count_triplets.cpp:103:13: warning: unused variable 'css' [-Wunused-variable]
103 | int css = compsize[i]-v.size();
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
55128 KB |
Output is correct |
| 2 |
Correct |
21 ms |
55088 KB |
Output is correct |
| 3 |
Correct |
20 ms |
55120 KB |
Output is correct |
| 4 |
Correct |
23 ms |
55368 KB |
Output is correct |
| 5 |
Correct |
21 ms |
55132 KB |
Output is correct |
| 6 |
Correct |
20 ms |
55132 KB |
Output is correct |
| 7 |
Incorrect |
20 ms |
55048 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
55128 KB |
Output is correct |
| 2 |
Correct |
21 ms |
55088 KB |
Output is correct |
| 3 |
Correct |
20 ms |
55120 KB |
Output is correct |
| 4 |
Correct |
23 ms |
55368 KB |
Output is correct |
| 5 |
Correct |
21 ms |
55132 KB |
Output is correct |
| 6 |
Correct |
20 ms |
55132 KB |
Output is correct |
| 7 |
Incorrect |
20 ms |
55048 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
71548 KB |
Output is correct |
| 2 |
Correct |
117 ms |
71504 KB |
Output is correct |
| 3 |
Incorrect |
145 ms |
73908 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
55384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
160 ms |
69004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
55408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
181 ms |
69220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
55128 KB |
Output is correct |
| 2 |
Correct |
21 ms |
55088 KB |
Output is correct |
| 3 |
Correct |
20 ms |
55120 KB |
Output is correct |
| 4 |
Correct |
23 ms |
55368 KB |
Output is correct |
| 5 |
Correct |
21 ms |
55132 KB |
Output is correct |
| 6 |
Correct |
20 ms |
55132 KB |
Output is correct |
| 7 |
Incorrect |
20 ms |
55048 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
55128 KB |
Output is correct |
| 2 |
Correct |
21 ms |
55088 KB |
Output is correct |
| 3 |
Correct |
20 ms |
55120 KB |
Output is correct |
| 4 |
Correct |
23 ms |
55368 KB |
Output is correct |
| 5 |
Correct |
21 ms |
55132 KB |
Output is correct |
| 6 |
Correct |
20 ms |
55132 KB |
Output is correct |
| 7 |
Incorrect |
20 ms |
55048 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
