이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 20;
vector<int> g[N], path;
int tin[N], f[N], timer;
int uin[N], uout[N], utm;
bool vis[N];
ll result;
vector<pair<int, int>> br;
int p[N], sz[N];
int root(int v){
if(p[v] == v)
return v;
return p[v] = root(p[v]);
}
void merge(int a, int b){
a = root(a);
b = root(b);
if(a == b)
return;
p[a] = b;
sz[b] += sz[a];
}
vector<int> cg[N]; // component-graph
void dfs(int v, int p){
vis[v] = true;
tin[v] = f[v] = ++ timer;
for(int x : g[v]){
if(x == p)
continue;
if(vis[x]){
f[v] = min(f[v], tin[x]);
}else{
dfs(x, v);
f[v] = min(f[v], f[x]);
}
}
if(p != -1){
if(f[v] <= tin[p]) // edge (p, v) is not a bridge
merge(v, p);
else
br.emplace_back(v, p);
}
}
int sub[N];
int to_comp[N], ptr;
int compsz[N];
void dfs2(int v, int p, int e){
vis[v] = true;
uin[v] = ++ utm;
sub[v] = sz[v];
to_comp[v] = e;
compsz[e] += sz[v];
for(int x : cg[v]){
if(x == p)
continue;
dfs2(x, v, e);
sub[v] += sub[x];
}
uout[v] = ++ utm;
}
bool upper(int a, int b){
return uin[a] <= uin[b] && uout[a] >= uout[b];
}
void dfs3(int v, int p){
vis[v] = true;
for(int x : cg[v]){
if(x == p)
continue;
// cout << v << " + " << 2ll * sub[x] * sz[v] * (n - sub[v]) << endl;
// cout << v << " + " << 2ll * sub[x] * sz[v] * (sub[v] - sub[x] - sz[v]) << endl;
result += 2ll * sub[x] * sz[v] * (compsz[to_comp[v]] - sub[v]);
result += 1ll * sub[x] * sz[v] * (sub[v] - sub[x] - sz[v]);
dfs3(x, v);
}
}
vector<int> xyz[N];
int main(){
ios_base :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i ++){
int u, v;
cin >> u >> v;
-- u; -- v;
g[v].push_back(u);
g[u].push_back(v);
}
iota(p, p + n, 0);
fill(sz, sz + n, 1);
fill(vis, vis + n, false);
for(int i = 0; i < n; i ++)
if(!vis[i])
dfs(i, -1);
for(auto [u, v] : br){
u = root(u);
v = root(v);
cg[u].push_back(v);
cg[v].push_back(u);
}
for(int i = 0; i < n; i ++)
xyz[root(i)].push_back(i);
// for(int i = 0; i < n; i ++)
// if(p[i] == i)
// cout << i << " : " << sz[i] << endl;
for(int i = 0; i < n; i ++){ // all in 1 component
if(p[i] == i && sz[i] >= 3)
result += 1ll * sz[i] * (sz[i] - 1) * (sz[i] - 2);
}
// cout << " - " << result << endl;
fill(vis, vis + n, false);
for(int i = 0; i < n; i ++)
if(!vis[i])
dfs2(root(i), -1, ptr ++);
for(int i = 0; i < n; i ++){ // 2 and 1 in different components
if(p[i] == i && sz[i] >= 2){
for(int j : xyz[i]){
int trash = 0;
for(int x : g[j]){
int h = root(x);
if(h != i){
trash += (upper(h, i) ? compsz[to_comp[i]] - sub[i] : sub[h]);
}
}
result += 2ll * (sz[i] - 1) * (compsz[to_comp[i]] - sz[i] - trash);
}
}
}
// cout << " - " << result << endl;
fill(vis, vis + n, false);
for(int i = 0; i < n; i ++)
if(!vis[i])
dfs3(root(i), -1);
cout << result;
}
# | 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... |