#include<bits/stdc++.h>
using namespace std;
#define int ll
#define ll long long
#define pii pair<int, int>
vector<vector<int>> graph;
vector<vector<int>> cgraph;
vector<vector<ll>> opt;
vector<int> comp;
vector<int> low;
vector<int> num;
vector<int> vis;
vector<int> art;
vector<ll> compsize;
stack<int> s;
int root = -1;
ll sol = 0;
int c = 0;
int d = 0;
ll n, m;
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])
{
dfs(ele, i);
if (low[ele]==num[i])
{
while(s.top() != ele)
{
comp[s.top()] = d;
compsize[d]++;
s.pop();
}
comp[ele] = d;
compsize[d]++;
s.pop();
d++;
}
}
low[i] = min(low[i], low[ele]);
}
if (num[i]==low[i])
{
art[d] = 1;
while (s.top() != i)
{
comp[s.top()] = d;
compsize[d]++;
s.pop();
}
comp[i] = d;
compsize[d]++;
s.pop();
d++;
}
}
void dfs2(int i, int p)
{
vis[i] = 1;
opt[i][0] = compsize[i];
opt[i][1] = (compsize[i]-1)*(compsize[i]-2) +compsize[i]-1;
if (!art[i]) opt[i][1] += compsize[i]-1;
sol += (compsize[i]-2)*compsize[i]*(compsize[i]-1);
if (!art[i]) sol += compsize[i]*(compsize[i]-1);
vector<array<ll, 2>> ones;
ll sum = 0;
for (int ele:cgraph[i])
{
if (vis[ele]) continue;
dfs2(ele, i);
opt[i][0] += opt[ele][0];
opt[i][1] += opt[ele][1] + opt[ele][0]*compsize[i];
sum += opt[ele][0];
ones.push_back({opt[ele][0], opt[ele][1]});
sol += opt[ele][0]*(compsize[i]-1)*(compsize[i]-2)*2;
sol += opt[ele][0]*(compsize[i]-1)*2;
if (!art[i]) sol += opt[ele][0]*(compsize[i]-1)*2;
sol += opt[ele][1]*compsize[i]*2;
}
for (array<ll, 2> ele:ones)
{
if (!art[i]) sol += ele[0]*(sum-ele[0])*(compsize[i]+1);
else sol += ele[0]*(sum-ele[0])*(compsize[i]);
sol += ele[1]*(sum-ele[0])*2;
}
}
int32_t main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin >> n >> m;
graph.assign(n, vector<int>());
cgraph.assign(n, vector<int>());
compsize.assign(n, 0);
low.assign(n, 0);
num.assign(n, 0);
comp.assign(n, -1);
vis.assign(n, 0);
art.assign(n, 0);
opt.assign(n, vector<ll>(2, 0));
vector<int> degree(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);
degree[a]++;
degree[b]++;
}
vector<pii> nodes;
for (int i= 0; i < n; i++) nodes.push_back({degree[i], i});
sort(nodes.begin(), nodes.end());
for (pii ele:nodes)
{
if (!num[ele.second])
{
dfs(ele.second, -1);
}
}
for (int i = 0; i <n; i++)
{
for (int ele:graph[i])
{
if (comp[i] == comp[ele]) continue;
cgraph[comp[i]].push_back(comp[ele]);
}
}
for (pii ele:nodes)
{
if (!vis[comp[ele.second]])
{
dfs2(comp[ele.second], -1);
}
}
cout << sol << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
113 ms |
29324 KB |
Output is correct |
2 |
Correct |
76 ms |
29380 KB |
Output is correct |
3 |
Correct |
122 ms |
29268 KB |
Output is correct |
4 |
Correct |
87 ms |
27332 KB |
Output is correct |
5 |
Correct |
81 ms |
26468 KB |
Output is correct |
6 |
Correct |
88 ms |
31424 KB |
Output is correct |
7 |
Correct |
87 ms |
26608 KB |
Output is correct |
8 |
Correct |
98 ms |
29008 KB |
Output is correct |
9 |
Correct |
95 ms |
25284 KB |
Output is correct |
10 |
Correct |
86 ms |
25792 KB |
Output is correct |
11 |
Correct |
78 ms |
24028 KB |
Output is correct |
12 |
Correct |
109 ms |
23828 KB |
Output is correct |
13 |
Correct |
80 ms |
24004 KB |
Output is correct |
14 |
Correct |
74 ms |
23664 KB |
Output is correct |
15 |
Correct |
60 ms |
22980 KB |
Output is correct |
16 |
Correct |
62 ms |
22724 KB |
Output is correct |
17 |
Correct |
20 ms |
18132 KB |
Output is correct |
18 |
Correct |
20 ms |
18128 KB |
Output is correct |
19 |
Correct |
20 ms |
18128 KB |
Output is correct |
20 |
Correct |
20 ms |
18132 KB |
Output is correct |
21 |
Correct |
21 ms |
18132 KB |
Output is correct |
22 |
Correct |
21 ms |
18132 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
696 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
704 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
696 KB |
Output is correct |
20 |
Correct |
1 ms |
600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
102 ms |
25028 KB |
Output is correct |
2 |
Correct |
95 ms |
24968 KB |
Output is correct |
3 |
Correct |
99 ms |
25116 KB |
Output is correct |
4 |
Correct |
101 ms |
25028 KB |
Output is correct |
5 |
Correct |
97 ms |
25124 KB |
Output is correct |
6 |
Correct |
118 ms |
37916 KB |
Output is correct |
7 |
Correct |
109 ms |
33788 KB |
Output is correct |
8 |
Correct |
106 ms |
28612 KB |
Output is correct |
9 |
Correct |
100 ms |
27332 KB |
Output is correct |
10 |
Correct |
96 ms |
25024 KB |
Output is correct |
11 |
Correct |
95 ms |
25028 KB |
Output is correct |
12 |
Correct |
115 ms |
25104 KB |
Output is correct |
13 |
Correct |
94 ms |
25024 KB |
Output is correct |
14 |
Correct |
88 ms |
25788 KB |
Output is correct |
15 |
Correct |
84 ms |
25076 KB |
Output is correct |
16 |
Correct |
59 ms |
22984 KB |
Output is correct |
17 |
Correct |
88 ms |
29764 KB |
Output is correct |
18 |
Correct |
92 ms |
29356 KB |
Output is correct |
19 |
Correct |
99 ms |
29488 KB |
Output is correct |
20 |
Correct |
87 ms |
28600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
97 ms |
25028 KB |
Output is correct |
2 |
Correct |
116 ms |
24804 KB |
Output is correct |
3 |
Incorrect |
109 ms |
24572 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |