oj.uz

Submission #958365

# Submission time Handle Problem Language Result Execution time Memory
958365 2024-04-05T14:29:56 Z rxlfd314 Duathlon (APIO18_duathlon) C++17
0 / 100
 68 ms 35320 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a,b,c,d) for (int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

constexpr int mxN=100000;
int N,M;
vt<ari2> adj[mxN];

int tin[mxN],stin[mxN],timer;
bool bridge[mxN<<1];
vt<int> added;
void find_bridges(int i,int p) {
  stin[i]=tin[i]=timer++;
  added.push_back(i);
  for(auto[j,k]:adj[i]){
    if(j==p)
      continue;
    if(tin[j]>=0)
      stin[i]=min(stin[i],tin[j]);
    else{
      find_bridges(j,i);
      stin[i]=min(stin[i],stin[j]);
      if(stin[j]>tin[i])
        bridge[k]=true;
    }
  }
}

int type[mxN];
void find_bcc(int i,int t){
  type[i]=t;
  for(auto[j,k]:adj[i])
    if(!bridge[k]&&type[j]<0)
      find_bcc(j,t);
}

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cin>>N>>M;
  FOR(i,0,M-1){
    int a,b;
    cin>>a>>b;
    adj[--a].push_back({--b,i});
    adj[b].push_back({a,i});
  }
  memset(tin,-1,sizeof(tin));
  memset(type,-1,sizeof(type));
  ll ans=0;
  FOR(r,0,N-1){
    if(tin[r]>=0)
      continue;
    added.clear();
    find_bridges(r,r);
    ans+=1ll*size(added)*(size(added)-1)*(size(added)-2);
    int B=0;
    for(int i:added)
      if(type[i]<0)
        find_bcc(i,B++);
    vt<vt<int>> bcc_adj(B),nodes(B);
    for(int i:added) {
      assert(type[i]>=0);
      nodes[type[i]].push_back(i);
      for(auto[j,k]:adj[i])
        if(bridge[k])
          bcc_adj[type[i]].push_back(type[j]);
    }
    #ifdef DEBUG
    cout<<"BCCs:\n";
    FOR(i,0,B-1){
      cout<<i<<':';
      for(int j:nodes[i])
        cout<<' '<<j+1;
      cout<<" |";
      for(int j:bcc_adj[i])
        cout<<' '<<j;
      cout<<'\n';
    }
    #endif
    vt<int> szs(B);
    function<void(int,int)> find_szs = [&](int i,int p){
      szs[i]=size(nodes[i]);
      for(int j:bcc_adj[i])
        if(j!=p){
          find_szs(j,i);
          szs[i]+=szs[j];
        }
    };
    find_szs(0,0);
    for(auto &vn:nodes){
      ll sub=0;
      for(int i:vn)
        for(auto[j,k]:adj[i])
          if(bridge[k]){
            if(szs[j]<szs[i])
              sub+=1ll*szs[j]*(szs[j]+1);
            else
              sub+=1ll*(szs[0]-szs[i])*(szs[0]-szs[i]+1);
          }
      for(int i:vn){
        ll s=sub;
        for(auto[j,k]:adj[i])
          if(bridge[k]){
            if(szs[j]<szs[i])
              s-=1ll*szs[j]*(szs[j]+1), s+=1ll*szs[j]*(szs[j]-1);
            else
              s-=1ll*(szs[0]-szs[i])*(szs[0]-szs[i]+1), s+=1ll*(szs[0]-szs[i])*(szs[0]-szs[i]-1);
          }
        #ifdef DEBUG
        cout<<"deleted from "<<i+1<<": "<<s<<'\n';
        #endif
        ans-=s;
      }
    }
  }
  cout<<ans<<'\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct
4 Correct 2 ms 4008 KB Output is correct
5 Correct 1 ms 4184 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Incorrect 2 ms 4188 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct
4 Correct 2 ms 4008 KB Output is correct
5 Correct 1 ms 4184 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Incorrect 2 ms 4188 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 17400 KB Output is correct
2 Correct 47 ms 17532 KB Output is correct
3 Runtime error 58 ms 35320 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 20940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 20940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct
4 Correct 2 ms 4008 KB Output is correct
5 Correct 1 ms 4184 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Incorrect 2 ms 4188 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct
4 Correct 2 ms 4008 KB Output is correct
5 Correct 1 ms 4184 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Incorrect 2 ms 4188 KB Output isn't correct
8 Halted 0 ms 0 KB -