이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define N 1000000
#define INF 1000000007
#define ff first
#define ss second
typedef long long ll;
using namespace std;
bool vis[N], bridge[N];
ll n, m, low[N], tin[N], h[N], sub[N], sz[N], timer, all, ans;
vector<pair<ll, ll> > adj[N];
vector<ll> adjt[N];
void dfs(ll node, ll par = 0){
timer++;
vis[node] = 1;
tin[node] = timer;
low[node] = tin[node];
for(pair<ll, ll> child: adj[node]){
ll to = child.ff;
if(to == par) continue;
if(vis[to] == 1){
low[node] = min(low[node], tin[to]);
}
else{
dfs(to, node);
low[node] = min(low[node], low[to]);
if(low[to] > tin[node]){
bridge[child.ss] = 1;
}
}
}
}
void dfs1(ll node, ll head){
h[node] = head;
vis[node] = 1;
sz[head]++;
for(pair<ll, ll> neigh : adj[node]){
if(bridge[neigh.ss] == 1 && vis[neigh.ff] == 0){
adjt[neigh.ff].push_back(head);
adjt[head].push_back(neigh.ff);
dfs1(neigh.ff, neigh.ff);
}
else{
if(vis[neigh.ff] == 0){
dfs1(neigh.ff, head);
}
}
}
}
void dfs2(ll node, ll par = 0){
// cout << node << ' ' << par << '\n';
vis[node] = 1;
sub[node] = sz[node];
for(ll to : adjt[node]){
if(to == par) continue;
dfs2(to, node);
sub[node] += sub[to];
}
// cout << sub[node] << ' ' << node << '\n';
}
void solve(ll node, ll par = 0){
ll g = 0, h = 0;
for(ll to : adjt[node]){
if(to == par) continue;
g += sub[to];
h += (sub[to] * sub[to]);
}
ans += ((g * g - h + (all - sub[node]) * g * 2) * sz[node]);
ans += (sz[node] * (sz[node] - 1) * (sz[node] - 2));
ans += (2 * (sz[node] - 1) * (sz[node] - 1) * (all - sz[node]));
for(ll to : adjt[node]){
if(to == par) continue;
solve(to, node);
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(ll i = 1; i <= m; i++){
ll x, y;
cin >> x >> y;
adj[x].push_back({y, i});
adj[y].push_back({x, i});
}
for(ll i = 1; i <= n; i++){
if(vis[i] == 0){
dfs(i);
}
}
memset(vis, 0, sizeof(vis));
for(ll i = 1; i <= n; i++){
if(vis[i] == 0){
dfs1(i, i);
}
}
memset(vis, 0, sizeof(vis));
for(ll i = 1; i <= n; i++){
if(vis[h[i]] == 0){
dfs2(h[i]);
all = sub[h[i]];
solve(h[i]);
}
}
cout << ans;
}
# | 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... |