oj.uz

답안 #977878

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
977878 2024-05-08T12:55:59 Z huutuan 철인 이종 경기 (APIO18_duathlon) C++14
0 / 100
 183 ms 123988 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=1e6+10;
int n, m;
vector<int> g[N];
int num[N], low[N], tdfs;
stack<pair<int, int>> stk;
vector<pair<int, int>> bcc[N];
int cnt=0, cc[N], sz[N];
bool joint[N];
vector<int> gg[N];

void dfs_joint(int u, int p){
   num[u]=low[u]=++tdfs;
   int child=0;
   for (int v:g[u]){
      if (v==p) continue;
      if (!num[v]){
         ++child;
         stk.emplace(u, v);
         dfs_joint(v, u);
         low[u]=min(low[u], low[v]);
         if (low[v]>=num[u]){
            joint[u]=1;
            ++cnt;
            pair<int, int> edge={-1, -1};
            do{
               edge=stk.top(); stk.pop();
               bcc[cnt].emplace_back(edge);
            }while (edge!=make_pair(u, v));
         }
      }else low[u]=min(low[u], num[v]);
   }
   if (!p) joint[u]=child>=2;
}

int ans;
int sub_sz[N];

void dfs_sz(int u, int p){
   sub_sz[u]=sz[u];
   for (int v:gg[u]) if (v!=p) dfs_sz(v, u), sub_sz[u]+=sub_sz[v];
}

void dfs(int u, int p){
   ans+=sz[u]*(sz[u]-1)*(sz[u]-2);
   ans+=sz[u]*(sz[u]-1)*(n-sz[u])*2;
   ans+=sz[u]*(n-sz[u])*(n-sz[u]-1);
   for (int v:gg[u]){
      int size=sub_sz[v];
      if (v==p) size=n-sub_sz[u];
      ans-=sz[u]*size*(size-1);
   }
   // if (u>n){
   //    for (int v:gg[u]){
   //       int size=sz[v];
   //       ans+=sz[u]*(size-1)*2;
   //    }
   // }
   if (u<=n){
      for (int v:gg[u]){
         ans+=sz[v]*(sz[v]-1);
      }
   }
   for (int v:gg[u]) if (v!=p) dfs(v, u);
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> m;
   for (int i=1; i<=m; ++i){
      int u, v; cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
   }
   dfs_joint(1, 0);
   set<pair<int, int>> edge;
   for (int i=1; i<=n; ++i) if (joint[i]) cc[i]=i;
   for (int i=1; i<=cnt; ++i){
      for (auto &j:bcc[i]){
         if (!joint[j.first]) cc[j.first]=n+i;
         else edge.emplace(n+i, j.first);
         if (!joint[j.second]) cc[j.second]=n+i;
         else edge.emplace(n+i, j.second);
      }
   }
   for (int i=1; i<=n; ++i) ++sz[cc[i]];
   for (auto &i:edge){
      gg[i.first].push_back(i.second);
      gg[i.second].push_back(i.first);
   }
   dfs_sz(n+1, 0);
   dfs(n+1, 0);
   cout << ans << '\n';
   return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 80056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 80056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 106720 KB Output is correct
2 Correct 87 ms 106584 KB Output is correct
3 Incorrect 54 ms 97996 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 80220 KB Output is correct
2 Correct 19 ms 80248 KB Output is correct
3 Correct 22 ms 80216 KB Output is correct
4 Correct 21 ms 80216 KB Output is correct
5 Correct 20 ms 80220 KB Output is correct
6 Correct 20 ms 80216 KB Output is correct
7 Correct 21 ms 80216 KB Output is correct
8 Correct 19 ms 80220 KB Output is correct
9 Correct 18 ms 80336 KB Output is correct
10 Incorrect 22 ms 79964 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 107852 KB Output is correct
2 Correct 133 ms 107748 KB Output is correct
3 Correct 110 ms 107948 KB Output is correct
4 Correct 135 ms 107852 KB Output is correct
5 Correct 147 ms 107864 KB Output is correct
6 Correct 177 ms 123988 KB Output is correct
7 Correct 142 ms 115256 KB Output is correct
8 Correct 183 ms 113288 KB Output is correct
9 Correct 115 ms 111612 KB Output is correct
10 Incorrect 80 ms 100000 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 80272 KB Output is correct
2 Correct 19 ms 80228 KB Output is correct
3 Incorrect 19 ms 80284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 107864 KB Output is correct
2 Correct 108 ms 108740 KB Output is correct
3 Incorrect 156 ms 106328 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 80056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 80056 KB Output isn't correct
2 Halted 0 ms 0 KB -