oj.uz

Submission #743323

# Submission time Handle Problem Language Result Execution time Memory
743323 2023-05-17T09:48:07 Z alvingogo Duathlon (APIO18_duathlon) C++14
8 / 100
 112 ms 47760 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

/*
1. tarjan find BCC(vertex)

2. block-cut tree
type, size, subtree size

3. dp
we iterate c
square -> s, t aren't in the same subtree -> add to all the circle connecting to the square
circle -> s, t aren't in the same subtree


done?
*/

vector<vector<int> > e,bcc; 
vector<int> low,dfn,cv;
int cnt=0,cc=0,cr=0;
stack<int> st;
void tj(int r,int f){
    int sl=0;
    cnt++;
    dfn[r]=low[r]=cnt;
    st.push(r);
    for(auto h:e[r]){
        if(h!=f){
            if(!dfn[h]){
                tj(h,r);
                sl++;
                low[r]=min(low[r],low[h]);
                if(low[h]>=dfn[r]){
                    if(f!=-1){
                        cr++;
                        cv[r]=cr;
                    }
                    bcc.push_back(vector<int>());
                    while(st.top()!=r){
                        bcc[cc].push_back(st.top());
                        st.pop();
                    }
                    bcc[cc].push_back(st.top());
                    cc++;
                }
            }
            else{
                low[r]=min(low[r],dfn[h]);
            }
        }
    }
    if(f==-1 && sl>=2){
        cr++;
        cv[r]=cr;
    }
    if(f==-1){
        st.pop();
    }
}

struct no{
    vector<int> ch;
    int t=0,sq=0;
    long long tp=0;
    int sz=1;
    int vis=0;
};
vector<no> v;
long long ans=0;
int dfs3(int r,int f){
    v[r].vis=1;
    if(v[r].t){
        v[r].sz=v[r].sq;
    }
    int k=v[r].sz;
    for(auto h:v[r].ch){
        if(h!=f){
            k+=dfs3(h,r);
        }
    }
    return k;
}
void dfs(int r,int f,int n){
    for(auto h:v[r].ch){
        if(h!=f){
            dfs(h,r,n);
            v[r].sz+=v[h].sz;
            if(v[r].t){
                v[r].tp+=1ll*v[h].sz*(v[h].sz-1);
            }
        }
    }
    if(v[r].t){
        v[r].tp+=1ll*(n-v[r].sz)*(n-v[r].sz-1);
        ans-=1ll*v[r].sq*v[r].tp;
    }
}
void dfs2(int r,int f,int n){
    for(auto h:v[r].ch){
        if(h!=f){
            dfs2(h,r,n);
            if(!v[r].t){
                ans-=(v[h].tp-1ll*(n-v[h].sz)*(n-v[h].sz-1));
            }
        }
    }
    if(!v[r].t){
        ans-=(v[f].tp-1ll*(v[r].sz)*(v[r].sz-1));
    }
}
signed main(){
    AquA;
    int n;
    cin >> n;
    if(n<3){
        cout << 0 << "\n";
        return 0;
    }
    int m;
    cin >> m;
    e.resize(n);
    low.resize(n);
    dfn.resize(n);
    cv.resize(n);
    for(int i=0;i<m;i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    for(int i=0;i<n;i++){
        if(!dfn[i]){
            tj(i,-1);
        }
    }
    assert(cc==bcc.size());
    int s=cc;
    for(int i=0;i<n;i++){
        if(cv[i]){
            s++;
        }
    }
    v.resize(s);
    for(int i=0;i<cc;i++){
        v[i].t=1;
        for(auto h:bcc[i]){
            if(cv[h]){
                v[i].ch.push_back(cv[h]+cc-1);
                v[cv[h]+cc-1].ch.push_back(i);
            }
            else{
                v[i].sq++;
            }
        }
    }
    for(int i=0;i<cc;i++){
        if(!v[i].vis){
            int k=dfs3(i,i);
            ans+=1ll*k*(k-1)*(k-2);
            dfs(i,i,k);
            dfs2(i,i,k);
        }
    }
    
    cout << ans << "\n";
    return 0;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from count_triplets.cpp:1:
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:145:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     assert(cc==bcc.size());
      |            ~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Runtime error 1 ms 468 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Runtime error 1 ms 468 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 21076 KB Output is correct
2 Correct 57 ms 21068 KB Output is correct
3 Correct 95 ms 28532 KB Output is correct
4 Correct 92 ms 23040 KB Output is correct
5 Correct 92 ms 21904 KB Output is correct
6 Correct 92 ms 30628 KB Output is correct
7 Correct 92 ms 26176 KB Output is correct
8 Correct 101 ms 28660 KB Output is correct
9 Correct 112 ms 24616 KB Output is correct
10 Correct 86 ms 23340 KB Output is correct
11 Correct 56 ms 17600 KB Output is correct
12 Correct 55 ms 17576 KB Output is correct
13 Correct 58 ms 16524 KB Output is correct
14 Correct 54 ms 16288 KB Output is correct
15 Correct 36 ms 13824 KB Output is correct
16 Correct 38 ms 13720 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 4 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 4 ms 4948 KB Output is correct
22 Correct 4 ms 4948 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 980 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 83 ms 47760 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1108 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 87 ms 47672 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Runtime error 1 ms 468 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Runtime error 1 ms 468 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -