이 제출은 이전 버전의 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], zam[100][100], cnt[15][15][15];
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);
}
}
void subtask1(){
int x[15];
for(int i = 1; i <= n; i++) x[i] = i;
do{
int last = n;
for(int i = 2; i <= n; i++){
if(zam[x[i]][x[i - 1]] != 1){
last = i - 1;
break;
}
}
for(int i = 1; i <= last; i++){
for(int j = i + 1; j <= last; j++){
for(int k = j + 1; k <= last; k++){
if(cnt[x[i]][x[j]][x[k]] == 0){
ans++;
cnt[x[i]][x[j]][x[k]] = 1;
}
}
}
}
}while(next_permutation(x + 1, x + n + 1));
cout << ans;
}
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;
if(x <= 10 && y <= 10){
zam[x][y] = 1;
zam[y][x] = 1;
}
adj[x].push_back({y, i});
adj[y].push_back({x, i});
}
if(n <= 10){
subtask1();
return 0;
}
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... |