Submission #492289

#	Time	Username	Problem	Language	Result	Execution time	Memory
492289		xyz	Duathlon (APIO18_duathlon)	C++17	31 / 100	1082 ms	24928 KiB

count_triplets

#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;

}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10