oj.uz

답안 #355202

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
355202 2021-01-22T10:08:15 Z oolimry 철인 이종 경기 (APIO18_duathlon) C++17
0 / 100
 196 ms 59048 KB 
#include <bits/stdc++.h>

using namespace std;
int n, m;
typedef vector<int> vi;
typedef pair<int,int> ii;
struct node{
  int depth = -1;
  int low;
  int parent;
  bool vis = false;
  bool isArti = false;
  vi adj;
};
vector<unordered_set<int> > biconnected;
stack<int> s; ///this is only needed for biconnected components
///note: this will ignore single nodes with no edges
static node g[200005];
int rootChildren = 0;
void dfs(int u){
  if(g[u].depth == -1) g[u].depth = g[g[u].parent].depth + 1;
  g[u].low = g[u].depth;
  g[u].vis = true;
  s.push(u);
  for(int i = 0;i < g[u].adj.size();i++){
    int v = g[u].adj[i];
    if(!g[v].vis){
      g[v].parent = u;
      if(g[u].depth == 0) rootChildren++;
      dfs(v);
      g[u].low = min(g[u].low,g[v].low);

      if(g[v].low >= g[u].depth){
        g[u].isArti = true;
        g[u].low = min(g[u].low,g[v].low);
        unordered_set<int> newSet;
        int nn;
        biconnected.push_back(newSet); ///create new biconnected component
        do{
          assert(!s.empty());
          nn = s.top();
          s.pop();
          biconnected.back().insert(nn);
        }while(nn != u);
      }
    }
    else if(v != g[u].parent){
      g[u].low = min(g[u].low,g[v].depth); ///g[v].depth not num!!!!!!
    }

  }
}
struct node2{
  long long sz;
  long long dp = 0;
  bool isArti = false;
  bool vis = false;
  int r;
  int p = -1;
  vi adj;
};

vector<node2> bct; ///block-cut tree
long long root = -1;
void dp(int u){
  if(bct[u].vis) return;
  bct[u].vis = true;
  bct[u].dp = bct[u].sz;
  bct[u].r = root;
  for(int i = 0;i < bct[u].adj.size();i++){
    int v = bct[u].adj[i];
    if(bct[v].vis) continue;
    bct[v].p = u;
    dp(v);
    bct[u].dp += bct[v].dp;
  }
}
int main()
{
  cin >> n >> m;
  ii edges[m];
  for(int i = 0;i < m;i++){
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].adj.push_back(b);
    g[b].adj.push_back(a);
    edges[i] = ii(a,b);
  }

  for(int i = 0;i < n;i++){
    if(!g[i].vis){
      rootChildren = 0;
      g[i].depth = 0;
      dfs(i);
      if(rootChildren > 1) g[i].isArti = true;
      else g[i].isArti = false; ///this line is needed
    }
  }
  unordered_map<int,int> artis;
  for(int i = 0;i < n;i++){
    if(g[i].isArti){
      artis[i] = bct.size();
      node2 nn;
      nn.sz = 1;
      nn.isArti = true;
      bct.push_back(nn);
    }
  }


  for(int i = 0;i < biconnected.size();i++){
    node2 nn;
    nn.sz = biconnected[i].size();
    nn.isArti = false;
    for(unordered_set<int>::iterator it = biconnected[i].begin();it != biconnected[i].end();it++){
      if(artis.find(*it) != artis.end()){
        nn.adj.push_back(artis[*it]);
        bct[artis[*it]].adj.push_back(bct.size());
        nn.sz--;
      }
    }
    bct.push_back(nn);
  }
  for(int i = 0;i < bct.size();i++){
    root = i;
    dp(i);
  }

  long long ans = 0ll;
  for(int i = 0;i < bct.size();i++){
    vector<long long> branches;
    vector<long long> branchStart;
    long long total = 0ll;
    for(int j = 0;j < bct[i].adj.size();j++){
      if(bct[i].adj[j] != bct[i].p){
        branches.push_back(bct[bct[i].adj[j]].dp);
        branchStart.push_back(bct[bct[i].adj[j]].sz);
      }
    }
    if(bct[i].p >= 0){
      branches.push_back(bct[bct[i].r].dp - bct[i].dp);
      branchStart.push_back(bct[bct[i].p].sz);
    }
    for(int j = 0;j < branches.size();j++) total += branches[j];
    long long extra = 0ll;
    if(!bct[i].isArti) extra = max(0ll,(long long)(bct[i].adj.size())-2);
    for(int j = 0;j < branches.size();j++){

      ///branch1 to self or neighbor articulation point to branch2
      ans += branches[j] * (total - branches[j]) * (bct[i].sz + extra);

      ///branch to self to self or self to self to branch
      ans += 2 * (bct[i].sz) * (bct[i].sz - 1) * branches[j];


      if(bct[i].isArti){
        ///direct branch to self to same branch(not reverse) or its reverse
        ans += 2ll * bct[i].sz * branchStart[j] * (branches[j] - branchStart[j]);
        ///direct branch to self to direct or its reverse
        ans += bct[i].sz * (branchStart[j]) * (branchStart[j] - 1);

      }
    }

    ///self to self to self
    ans += (bct[i].sz) * (bct[i].sz - 1) * (bct[i].sz - 2);
  }
  cout << ans;
}

Compilation message

count_triplets.cpp: In function 'void dfs(int)':
count_triplets.cpp:25:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for(int i = 0;i < g[u].adj.size();i++){
      |                 ~~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dp(int)':
count_triplets.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for(int i = 0;i < bct[u].adj.size();i++){
      |                 ~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:113:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::unordered_set<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for(int i = 0;i < biconnected.size();i++){
      |                 ~~^~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:126:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |   for(int i = 0;i < bct.size();i++){
      |                 ~~^~~~~~~~~~~~
count_triplets.cpp:132:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |   for(int i = 0;i < bct.size();i++){
      |                 ~~^~~~~~~~~~~~
count_triplets.cpp:136:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for(int j = 0;j < bct[i].adj.size();j++){
      |                   ~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp:146:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for(int j = 0;j < branches.size();j++) total += branches[j];
      |                   ~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:149:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     for(int j = 0;j < branches.size();j++){
      |                   ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8172 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 6 ms 8172 KB Output is correct
5 Correct 6 ms 8172 KB Output is correct
6 Correct 6 ms 8172 KB Output is correct
7 Runtime error 16 ms 16364 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8172 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 6 ms 8172 KB Output is correct
5 Correct 6 ms 8172 KB Output is correct
6 Correct 6 ms 8172 KB Output is correct
7 Runtime error 16 ms 16364 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 156 ms 34788 KB Output is correct
2 Correct 159 ms 34724 KB Output is correct
3 Runtime error 196 ms 59048 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 18 ms 16540 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 138 ms 25836 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 17 ms 16364 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 124 ms 25836 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8172 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 6 ms 8172 KB Output is correct
5 Correct 6 ms 8172 KB Output is correct
6 Correct 6 ms 8172 KB Output is correct
7 Runtime error 16 ms 16364 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8172 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 6 ms 8172 KB Output is correct
5 Correct 6 ms 8172 KB Output is correct
6 Correct 6 ms 8172 KB Output is correct
7 Runtime error 16 ms 16364 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -