이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
//#define FILE_IO
typedef long long LL;
int N, M;
namespace Biconnex
{
int h[100005], low[100005];
vector<int> edg[100005];
stack<int> stv;
int K = 0;
vector<int> bcx[100005], cmp[100005];
void addEdge(int x, int y)
{
edg[x].push_back(y);
edg[y].push_back(x);
}
void DFS(int nod, int fth = 0)
{
h[nod] = h[fth] + 1;
low[nod] = h[nod];
stv.push(nod);
for(auto nxt: edg[nod])
{
if(nxt == fth) continue;
if(h[nxt] != 0) { low[nod] = min(low[nod], h[nxt]); continue; }
stv.push(nod);
DFS(nxt, nod);
low[nod] = min(low[nod], low[nxt]);
if(low[nxt] >= h[nod])
{
K++;
while(stv.top() != nod)
{
int x = stv.top();
cmp[K].push_back(x);
bcx[x].push_back(K);
stv.pop();
}
cmp[K].push_back(nod);
bcx[nod].push_back(K);
stv.pop();
}
}
}
void getbiconnex()
{
for(int i = 1; i <= N; i++)
if(!h[i])
DFS(i);
for(int i = 1; i <= K; i++)
cmp[i].erase(unique(cmp[i].begin(), cmp[i].end()), cmp[i].end());
for(int i = 1; i <= N; i++)
bcx[i].erase(unique(bcx[i].begin(), bcx[i].end()), bcx[i].end());
}
}
namespace Tree
{
int N, K;
LL ans;
int f[200005], viz[200005];
int valuare[200005], val[200005], sz[200005], cmp[200005];
vector<int> edg[200005];
void addEdge(int x, int y)
{
f[x] = f[y] = 1;
edg[x].push_back(y);
edg[y].push_back(x);
}
void setValue(int x, int y) { val[x] = y; }
void DFS(int nod, int fth = 0)
{
if(fth == 0) cmp[nod] = nod;
else cmp[nod] = cmp[fth];
viz[nod] = 1;
valuare[nod] = val[nod] == -1 ? 1 : val[nod] - edg[nod].size();
sz[nod] = valuare[nod];
for(auto nxt: edg[nod])
{
if(nxt == fth) continue;
DFS(nxt, nod);
sz[nod] += sz[nxt];
}
}
void solve()
{
ans = 0;
for(int i = 1; i <= N + K; i++)
if(f[i] && !viz[i])
DFS(i);
for(int i = N + 1; i <= N + K; i++)
if(f[i])
ans += val[i] * (val[i] - 1) * (val[i] - 2);
for(int i = 1; i <= N; i++)
if(f[i])
{
int nod = i;
int M = sz[ cmp[i] ];
for(auto nxt: edg[i])
{
if(sz[nxt] > sz[nod]) continue;
ans += 1LL * sz[nxt] * (M - sz[nxt] - 1);
}
ans += 1LL * (sz[nod] - 1) * (M - sz[nod]);
}
for(int i = N + 1; i <= N + K; i++)
if(f[i])
{
int nod = i;
int M = sz[ cmp[i] ];
for(auto nxt: edg[i])
{
if(sz[nxt] > sz[nod]) continue;
ans += 1LL * (sz[nxt] - 1) * (M - sz[nxt] + 1 - val[nod]) * valuare[i];
}
ans += 1LL * valuare[i] * (M - sz[nod] - 1) * (sz[nod] - val[nod] + 1);
for(auto nxt: edg[i])
{
if(sz[nxt] > sz[nod]) continue;
ans += 1LL * (val[i] - 1) * (val[i] - 2) * (sz[nxt] - 1);
}
ans += 1LL * (val[i] - 1) * (val[i] - 2) * (M - sz[nod] - 1);
}
printf("%lld\n", ans);
}
}
void makeTree()
{
using namespace Biconnex;
for(int i = 1; i <= N; i++)
Tree::setValue(i, -1);
for(int i = 1; i <= K; i++)
{
if(cmp[i].size() > 2)
{
Tree::setValue(i + N, cmp[i].size());
for(auto &nod: cmp[i])
if(bcx[nod].size() > 1)
Tree::addEdge(i + N, nod);
}
else
{
Tree::addEdge(cmp[i][0], cmp[i][1]);
}
}
Tree::N = N;
Tree::K = K;
}
int main()
{
#ifdef FILE_IO
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
scanf("%d%d", &N, &M);
for(int i = 1; i <= M; i++)
{
int x, y;
scanf("%d%d", &x, &y);
Biconnex::addEdge(x, y);
}
Biconnex::getbiconnex();
makeTree();
Tree::solve();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:179:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
count_triplets.cpp:183:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
# | 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... |