Submission #49505

#	Time	Username	Problem	Language	Result	Execution time	Memory
49505		mirbek01	Duathlon (APIO18_duathlon)	C++17	66 / 100	702 ms	52332 KiB

count_triplets

# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

int n, m, used[11][N], root, vis[N];
int tin[N], fup[N], timer;
int p[N], sz[N], siz[N], P[N], SZ[N];
long long ans;
map < pair <int, int>, bool > isb, ISB;
vector <int> g[N], gr[N], vr[N], G[N];

int get(int v){
      return (p[v] == v)?v:p[v] = get(p[v]);
}
void unite(int a, int b){
      a = get(a);
      b = get(b);
      if(a != b){
            if(sz[b] > sz[a]) swap(a, b);
            p[b] = a;
            sz[a] += sz[b];
      }
}
int f_s(int v){
      return (P[v] == v)?v:P[v] = f_s(P[v]);
}
void u_s(int a, int b){
      a = f_s(a);
      b = f_s(b);
      if(a != b){
            if(SZ[a] > SZ[b]) swap(a, b);
            P[b] = a;
            SZ[a] += SZ[b];
      }
}

void dfs(int v, int pr = 0){
      used[0][v] = 1;
      tin[v] = fup[v] = ++ timer;
      for(int to : g[v]){
            if(to == pr) continue;
            if(used[0][to])
                  fup[v] = min(fup[v], tin[to]);
            else {
                  dfs(to, v);
                  fup[v] = min(fup[v], fup[to]);
                  if(fup[to] > tin[v]){
                        isb[{v, to}] = 1;
                        isb[{to, v}] = 1;
                  }
            }
      }
}


void dfs1(int v){
      used[1][v] = 1;
      for(int to : g[v]){
            if(used[1][to]) continue;
            if(!isb[{v, to}])
                  unite(v, to);
            dfs1(to);
      }
}

void dfs2(int v){
      used[2][v] = 1;
      vr[get(v)].push_back(v);
      for(int to : g[v]){
            if(used[2][to]) continue;
            if(get(v) != get(to)){
                  gr[get(v)].push_back(get(to));
                  gr[get(to)].push_back(get(v));
            }
            dfs2(to);
      }
}

void dfs3(int v){
      used[3][v] = 1;
      siz[v] = sz[v];
      for(int to : gr[v]){
            if(used[3][to]) continue;
            dfs3(to);
            siz[v] += siz[to];
      }
}

void dfs5(int v){
      used[4][v] = 1;
      for(int to : g[v])
            if(vis[v] == vis[to] && get(v) == get(to) && !used[4][to]){
                  u_s(v, to);
                  dfs5(to);
            }
}

void dfs6(int v){
      used[5][v] = 1;
      for(int to : g[v]){
            if(used[5][to] || get(v) != get(to)) continue;
            if(f_s(v) != f_s(to)){
                  G[f_s(v)].push_back(f_s(to));
                  G[f_s(to)].push_back(f_s(v));
            }
            dfs6(to);
      }
}

void dfs7(int v){
      used[6][v] = 1;
      sort(G[v].begin(), G[v].end());
      G[v].resize(unique(G[v].begin(), G[v].end()) - G[v].begin());
      for(int to : G[v]){
            if(used[6][to]) continue;
            dfs7(to);
      }
}

int TIN[N], FUP[N], TIMER;

void dfs8(int v, int pr = 0){
      used[7][v] = 1;
      TIN[v] = FUP[v] = ++ TIMER;
      for(int to : G[v]){
            if(to == pr) continue;
            if(used[7][to])
                  FUP[v] = min(FUP[v], TIN[v]);
            else {
                  dfs8(to, v);
                  FUP[v] = min(FUP[v], FUP[to]);
                  if(FUP[to] > TIN[v]){
                        ISB[{v, to}] = 1;
                        ISB[{to, v}] = 1;
                  }
            }
      }
}

void dfs9(int v){
      used[8][v] = 1;
      for(int to : G[v]){
            if(used[8][to]) continue;
            if(!ISB[{v, to}])
                  u_s(v, to);
            dfs9(to);
      }
}

int Sz, sZ[N], A[N];

void dfs10(int v, int pr = 0){
      used[9][v] = 1;
      for(int to : G[v]){
            if(pr == to) continue;
            if(used[9][to]) {
                  if(vis[to] && f_s(v) != f_s(to)) Sz += sZ[to];
            } else
                  if(f_s(v) == f_s(to))
                        dfs10(to);
                  else {
                        if(vis[to]) Sz += sZ[to];
                  }
      }
}

int Fup[N], Tin[N], Timer;

void dfs11(int v, int pr = 0){
      used[10][v] = 1;
      Fup[v] = Tin[v] = ++ Timer;
      int children = 0;
      for(int to : g[v]){
            if(to == pr || get(v) != get(to)) continue;
            if(used[10][to])
                  Fup[v] = min(Fup[v], Tin[to]);
            else {
                  dfs11(to, v);
                  Fup[v] = min(Fup[v], Fup[to]);
                  if(Fup[to] >= Tin[v] && pr)
                        vis[v] = 1;
                  children ++;
            }
      }
      if(children > 1 && !pr)
            vis[v] = 1;
}

void dfs4(int v, int pr = 0){
      ans += sz[v] * 1ll * (sz[v] - 1) * 1ll * (sz[v] - 2);
      dfs11(v);
      for(int i : vr[v])
            if(!used[4][i])
                  dfs5(i);
      dfs6(vr[v].front());
      dfs7(f_s(vr[v].front()));
      dfs8(f_s(vr[v].front()));
      for(int i : vr[v]){
            sZ[f_s(i)] = SZ[f_s(i)], A[i] = P[i];
      }
      dfs9(f_s(vr[v].front()));
      for(int i : vr[v]){
            if(!used[9][A[i]]){
                  Sz = SZ[f_s(i)];
                  dfs10(A[i]);
                  ans -= Sz * (Sz - 1) * (sz[v] - Sz);
            }
      }
      int S = 0;
      vector <int> vv;
      for(int i : vr[v]){
            vector <int> vec;
            int sum = 0;
            for(int to : g[i])
                  if(get(to) != get(i)){
                        if(get(to) == pr){
                              sum += siz[root] - siz[v];
                              vec.push_back(siz[root] - siz[v]);
                        } else {
                              sum += siz[get(to)];
                              vec.push_back(siz[get(to)]);
                        }
                  }
            for(int j : vec)
                  ans += j * 1ll * (sum - j);
            S += sum;
            vv.push_back(sum);
      }
      long long cur = 0;
      for(int i : vv)
            cur += i * 1ll * (S - i);
      ans += cur * 1ll * sz[v];
      long long cost = sz[v] - 1 + (sz[v] - 1) * 1ll * (sz[v] - 2);
      cost *= 2;
      ans += (siz[root] - siz[v]) * 1ll * cost;
      for(int to : gr[v]){
            if(to == pr) continue;
            ans += cost * 1ll * siz[to];
            dfs4(to, v);
      }
}

int main(){
      scanf("%d %d", &n, &m);

      for(int i = 1; i <= m; i ++){
            int u, v;
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
      }

      for(int i = 1; i <= n; i ++)
            p[i] = P[i] = i, sz[i] = SZ[i] = 1;

      for(int i = 1; i <= n; i ++){
            if(!used[0][i]){
                  dfs(i);
                  dfs1(i);
                  dfs2(i);
                  root = get(i);
                  dfs3(get(i));
                  dfs4(get(i));
            }
      }

      cout << ans << endl;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:246:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &n, &m);
       ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:250:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~~

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