이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5+10;
int n;
int in[maxn], low[maxn], id[maxn], tt, cc;
bool is[maxn];
int sz[maxn], sub[maxn];
int comp_tree[maxn], sz_comp[maxn];
bool solved[maxn];
vector<int> grafo[maxn], tree[maxn], stk;
vector<vector<int>> comp;
void dfs(int u, int p)
{
in[u] = low[u] = ++tt;
stk.push_back(u);
for (auto v: grafo[u])
{
if (v == p) continue;
if (in[v]) low[u] = min(low[u], in[v]);
else
{
dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= in[u])
{
is[u] = (in[u] > 1 || in[v] > 2);
comp.push_back({u});
while (stk.back() != u)
{
comp.back().push_back(stk.back());
stk.pop_back();
}
}
}
}
}
void build(void)
{
for (int i = 1; i <= n; i++)
{
if (is[i])
{
id[i] = ++cc;
sz[cc]++;
}
}
for (auto &C: comp)
{
cc++;
for (auto u: C)
{
if (!is[u])
{
id[u] = cc;
sz[cc]++;
}
else
{
tree[id[u]].push_back(cc);
tree[cc].push_back(id[u]);
}
}
}
}
ll ans;
ll choose2(int n)
{
return 1ll*n*(n-1)/2ll;
}
ll choose3(int n)
{
return 1ll*n*(n-1)*(n-2)/6ll;
}
void calc(int u, int p, int cc)
{
comp_tree[u] = cc;
sz_comp[cc] += sz[u];
sub[u] = sz[u];
for (auto v: tree[u])
{
if (v == p) continue;
calc(v, u, cc);
sub[u] += sub[v];
}
}
void solve(int u, int p)
{
solved[comp_tree[u]] = 1;
ans += 2ll*choose2(sz[p])*sz[u];
if (sz[u] >= 3) ans += 6ll*choose3(sz[u]);
if (sz[u] >= 2) ans += 4ll*choose2(sz[u])*(sub[u]-sz[u] + sz_comp[comp_tree[u]]-sub[u]);
ans += 2ll*sz[u]*(sz_comp[comp_tree[u]]-sub[u])*(sub[u]-sz[u]);
int soma = 0;
for (auto v: tree[u])
{
if (v == p) continue;
ans += 2ll*sz[u]*soma*sub[v];
soma += sub[v];
ans += 2ll*choose2(sz[v])*sz[u];
solve(v, u);
}
}
int main(void)
{
int m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++)
{
int u, v;
scanf("%d %d", &u, &v);
grafo[u].push_back(v);
grafo[v].push_back(u);
}
for (int i = 1; i <= n; i++)
if (!in[i])
dfs(i, 0);
build();
int cc_tree = 0;
for (int i = 1; i <= 2*n; i++)
if (!comp_tree[i])
calc(i, 0, ++cc_tree);
for (int i = 1; i <= 2*n; i++)
if (!solved[comp_tree[i]])
solve(i, 0);
printf("%lld\n", ans);
}
컴파일 시 표준 에러 (stderr) 메시지
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:144:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
144 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:149:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
149 | scanf("%d %d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |