oj.uz

Submission #742261

# Submission time Handle Problem Language Result Execution time Memory
742261 2023-05-16T03:12:58 Z victor_gao Duathlon (APIO18_duathlon) C++17
31 / 100
 125 ms 35612 KB 
//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 200015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,m,dfn[N],low[N],boss[N],sz[N],cont[N],nbcc=0,t=0,ans=0;
bool vis[N];
stack<int>st;
vector<int>g[N],bcc[N];
vector<int>G[N];
vector<pii>edge;
void tarjan(int p,int lp){
    dfn[p]=low[p]=++t;
    st.push(p);
    for (auto i:g[p]){
        if (!dfn[i]){
            tarjan(i,p);
            low[p]=min(low[p],low[i]);
        }
        else if (i!=lp&&dfn[i]<dfn[p])
            low[p]=min(low[p],dfn[i]);
    }
    if (dfn[p]==low[p]){
        nbcc++;
        for (int x=0;x!=p;st.pop()){
            x=st.top(); boss[x]=nbcc; cont[nbcc]++;
            bcc[nbcc].push_back(x);
        }
    }
}
void build(){
    for (auto [a,b]:edge){
        if (boss[a]!=boss[b]){
            G[boss[a]].push_back(boss[b]);
            G[boss[b]].push_back(boss[a]);
        }
    }
}
void dfs(int p,int lp){
    sz[p]=cont[p]; vis[p]=1;
    for (auto i:G[p]){
        if (i!=lp){
            dfs(i,p);
            sz[p]+=sz[i];
        }
    }
}
void dfs1(int p,int lp){
    sz[p]+=sz[lp];
    int tans=0;
    for (auto i:G[p]){
        tans=(tans+(cont[p]-1)*sz[i]*2+(cont[p]-1)*(cont[p]-2)*sz[i]*2);
        tans=(tans+cont[p]*(sz[p]-cont[p]-sz[i])*sz[i]);
    }
    ans=(ans+tans);
    for (auto i:G[p]){
        if (i!=lp){
            sz[p]-=sz[i];
            dfs1(i,p);
            sz[p]+=sz[i];
        }
    }
    sz[p]-=sz[lp];
}
signed main(){
    fast
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int a,b; cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
        edge.push_back({a,b});
    }
    for (int i=1;i<=n;i++){
        if (!dfn[i]) tarjan(i,0);
    }
    build();
    for (int i=1;i<=nbcc;i++){
        if (!vis[i]){
            dfs(i,0); dfs1(i,0);
        }
    }
    for (int i=1;i<=nbcc;i++){
        ans=(ans+cont[i]*(cont[i]-1)*(cont[i]-2));
    }
    cout<<ans<<'\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 9 ms 14420 KB Output is correct
5 Correct 8 ms 14428 KB Output is correct
6 Correct 9 ms 14328 KB Output is correct
7 Incorrect 7 ms 14372 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 9 ms 14420 KB Output is correct
5 Correct 8 ms 14428 KB Output is correct
6 Correct 9 ms 14328 KB Output is correct
7 Incorrect 7 ms 14372 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 33424 KB Output is correct
2 Correct 62 ms 33504 KB Output is correct
3 Correct 93 ms 30472 KB Output is correct
4 Correct 74 ms 32268 KB Output is correct
5 Correct 79 ms 28108 KB Output is correct
6 Correct 79 ms 30004 KB Output is correct
7 Correct 99 ms 28772 KB Output is correct
8 Correct 99 ms 29528 KB Output is correct
9 Correct 78 ms 27940 KB Output is correct
10 Correct 99 ms 28024 KB Output is correct
11 Correct 87 ms 26636 KB Output is correct
12 Correct 61 ms 26424 KB Output is correct
13 Correct 59 ms 26772 KB Output is correct
14 Correct 60 ms 26492 KB Output is correct
15 Correct 51 ms 26628 KB Output is correct
16 Correct 63 ms 26176 KB Output is correct
17 Correct 16 ms 21592 KB Output is correct
18 Correct 20 ms 21588 KB Output is correct
19 Correct 19 ms 21588 KB Output is correct
20 Correct 21 ms 21480 KB Output is correct
21 Correct 15 ms 21584 KB Output is correct
22 Correct 16 ms 21548 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 8 ms 14548 KB Output is correct
3 Correct 8 ms 14548 KB Output is correct
4 Correct 8 ms 14676 KB Output is correct
5 Correct 8 ms 14636 KB Output is correct
6 Correct 8 ms 14608 KB Output is correct
7 Correct 8 ms 14672 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 10 ms 14548 KB Output is correct
10 Correct 8 ms 14548 KB Output is correct
11 Correct 8 ms 14556 KB Output is correct
12 Correct 8 ms 14560 KB Output is correct
13 Correct 9 ms 14556 KB Output is correct
14 Correct 9 ms 14556 KB Output is correct
15 Correct 9 ms 14548 KB Output is correct
16 Correct 9 ms 14548 KB Output is correct
17 Correct 10 ms 14624 KB Output is correct
18 Correct 8 ms 14560 KB Output is correct
19 Correct 9 ms 14548 KB Output is correct
20 Correct 7 ms 14548 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 30612 KB Output is correct
2 Correct 106 ms 30520 KB Output is correct
3 Correct 87 ms 30508 KB Output is correct
4 Correct 94 ms 30580 KB Output is correct
5 Correct 104 ms 30604 KB Output is correct
6 Correct 125 ms 35612 KB Output is correct
7 Correct 96 ms 33772 KB Output is correct
8 Correct 98 ms 32848 KB Output is correct
9 Correct 96 ms 31952 KB Output is correct
10 Correct 119 ms 30556 KB Output is correct
11 Correct 92 ms 31200 KB Output is correct
12 Correct 90 ms 31164 KB Output is correct
13 Correct 106 ms 31252 KB Output is correct
14 Correct 99 ms 30560 KB Output is correct
15 Correct 77 ms 29976 KB Output is correct
16 Correct 49 ms 27780 KB Output is correct
17 Correct 64 ms 31556 KB Output is correct
18 Correct 78 ms 31564 KB Output is correct
19 Correct 80 ms 32256 KB Output is correct
20 Correct 63 ms 31608 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 9 ms 14548 KB Output is correct
3 Incorrect 8 ms 14548 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 30520 KB Output is correct
2 Correct 94 ms 30340 KB Output is correct
3 Incorrect 82 ms 28224 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 9 ms 14420 KB Output is correct
5 Correct 8 ms 14428 KB Output is correct
6 Correct 9 ms 14328 KB Output is correct
7 Incorrect 7 ms 14372 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 9 ms 14420 KB Output is correct
5 Correct 8 ms 14428 KB Output is correct
6 Correct 9 ms 14328 KB Output is correct
7 Incorrect 7 ms 14372 KB Output isn't correct
8 Halted 0 ms 0 KB -