Submission #260964

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
260964	2020-08-11T08:46:12 Z	emanIaicepsa	Duathlon (APIO18_duathlon)	C++14	66 / 100	222 ms	25448 KB

count_triplets

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define vi vector<int>
#define pb emplace_back
#define fi first
#define se second
#define all(n) (n).begin(),(n).end()
#define mem(n,m) memset(n,m,sizeof(n))
#define IOS ios::sync_with_stdio(0), cin.tie(0)
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
template<typename A> void _do(A x){cerr<<x<<'\n';}
template<typename A,typename ...B> void _do(A x,B ...y){cerr<<x<<", ";_do(y...);}

const int mxn = 100005;
ll C(ll x){
    return (x)*(x-1)*(x-2)/6*2;
}

ll P(ll x){
    return C(x)*3;
}

ll n,m;
vi E[mxn], E2[mxn];
ll siz[mxn], ans=0, l[mxn], d[mxn], bcc[mxn], bcc_siz[mxn], dfn, bccid, vis[mxn], rt[mxn], siznd[mxn];
stack<int> s;

void dfs(int x,int p){
    l[x] = d[x] = ++dfn;
    siznd[x] = 1;
    s.push(x);
    for(auto i:E[x]){
        if(i==p) continue;
        if(!d[i]){
            dfs(i,x);
            siznd[x] += siznd[i];
            l[x] = min(l[x],l[i]);
        }
        else{
            l[x] = min(l[x],d[i]);
        }
    }
    if(l[x] == d[x]){
        bccid++;
        for(int i;i!=x;){
            i = s.top(); s.pop();
            bcc[i] = bccid;
        }
    }
}

void bcc_dfs(int x,int p,int anc){
    rt[x] = anc;
    siz[x] = bcc_siz[x];
    vis[x] = 1;
    for(auto i:E2[x]){
        if(i==p) continue;
        bcc_dfs(i,x,anc);
        siz[x] += siz[i];
    }
}

void bcc_dfs2(int x,int p,int anc){
    vis[x] = 1;
    for(auto i:E2[x]){
        if(i==p) continue;
        bcc_dfs2(i,x,anc);
        ans += siz[i] * (siz[anc] - siz[i] - bcc_siz[x]) * bcc_siz[x];
    }
    ans += (siz[x]-bcc_siz[x]) * (siz[anc]-siz[x]) * bcc_siz[x];
}

void dfs3(int x,int p,int anc){
    vis[x] = 1;
    ll allsiz = 0;
    vi tmp;
    for(auto i:E[x]){
        if(i==p || vis[i]) continue;
        dfs3(i,x,anc);
        if(bcc[i] != bcc[x]){
            allsiz += siznd[i];
            tmp.pb(siznd[i]);
        }
        //ans -= siznd[i] * (siznd[x] - siznd[i] - 1) * (bcc_siz[bcc[x]] - 1);
    }
    if(bcc[p] != bcc[x]){
        allsiz += siznd[anc] - siznd[x];
        tmp.pb(siznd[anc] - siznd[x]);
    }

    for(auto i:tmp){
        ans -= (i) * (allsiz-i) * (bcc_siz[bcc[x]] - 1);
    }

}

signed main(){
	IOS;
    cin>>n>>m;
    for(int i=1,a,b;i<=m;i++){
        cin>>a>>b;
        E[a].pb(b);
        E[b].pb(a);
    }


    for(int i=1;i<=n;i++) if(!d[i]) dfs(i,0);

    for(int i=1;i<=n;i++){
        //dbg(i, bcc[i]);
        bcc_siz[bcc[i]]++;
        for(auto j:E[i]){
            if(bcc[i] == bcc[j]) continue;
            E2[bcc[i]].pb(bcc[j]);
            E2[bcc[j]].pb(bcc[i]);
        }
    }

    for(int i=1;i<=bccid;i++){
        sort(all(E2[i]));
        E2[i].resize(unique(all(E2[i]))-E2[i].begin());
    }

    for(int i=1;i<=bccid;i++){
        if(!vis[i]){
            bcc_dfs(i,0,i);
        }
    }
//    for(int i=1;i<=bccid;i++){
//        dbg(i, siz[i]);
//    }
    mem(vis,0);
    for(int i=1;i<=bccid;i++){
        if(bcc_siz[i]>=3){
            ll x = bcc_siz[i];
            ans += P(x);
            ans += (x-1) * (x-1) * (siz[rt[i]] - x) * 2;
        }
        if(!vis[i]){
            bcc_dfs2(i,0,i);
        }
    }
    //dbg(ans);
    mem(vis,0);
    for(int i=1;i<=n;i++){
        if(!vis[i]) dfs3(i,0,i);
    }
    //dbg(ans);

    cout<<ans<<'\n';

}
/*
3 3
1 2
2 3
3 1

4 4
1 2
2 3
3 4
2 4

5 4
1 2
2 3
1 3
4 5

7 8
1 2
1 3
2 3
2 4
2 7
4 5
4 6
5 6
*/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	102 ms	23364 KB	Output is correct
2	Correct	108 ms	24132 KB	Output is correct
3	Correct	142 ms	21240 KB	Output is correct
4	Correct	124 ms	22392 KB	Output is correct
5	Correct	126 ms	18296 KB	Output is correct
6	Correct	151 ms	20220 KB	Output is correct
7	Correct	153 ms	18208 KB	Output is correct
8	Correct	148 ms	19168 KB	Output is correct
9	Correct	142 ms	17148 KB	Output is correct
10	Correct	160 ms	17656 KB	Output is correct
11	Correct	107 ms	15864 KB	Output is correct
12	Correct	98 ms	15736 KB	Output is correct
13	Correct	92 ms	16120 KB	Output is correct
14	Correct	105 ms	15992 KB	Output is correct
15	Correct	83 ms	15996 KB	Output is correct
16	Correct	89 ms	15608 KB	Output is correct
17	Correct	14 ms	11264 KB	Output is correct
18	Correct	14 ms	11264 KB	Output is correct
19	Correct	14 ms	11264 KB	Output is correct
20	Correct	14 ms	11264 KB	Output is correct
21	Correct	15 ms	11264 KB	Output is correct
22	Correct	14 ms	11264 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	6016 KB	Output is correct
2	Correct	4 ms	6016 KB	Output is correct
3	Correct	5 ms	6016 KB	Output is correct
4	Correct	5 ms	6016 KB	Output is correct
5	Correct	5 ms	6016 KB	Output is correct
6	Correct	4 ms	6016 KB	Output is correct
7	Correct	4 ms	6036 KB	Output is correct
8	Correct	5 ms	6016 KB	Output is correct
9	Correct	5 ms	6016 KB	Output is correct
10	Correct	5 ms	6016 KB	Output is correct
11	Correct	4 ms	6016 KB	Output is correct
12	Correct	5 ms	6016 KB	Output is correct
13	Correct	5 ms	6016 KB	Output is correct
14	Correct	4 ms	6016 KB	Output is correct
15	Correct	5 ms	6016 KB	Output is correct
16	Correct	4 ms	5888 KB	Output is correct
17	Correct	5 ms	6016 KB	Output is correct
18	Correct	5 ms	6016 KB	Output is correct
19	Correct	4 ms	6016 KB	Output is correct
20	Correct	4 ms	6016 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	165 ms	18348 KB	Output is correct
2	Correct	177 ms	18552 KB	Output is correct
3	Correct	172 ms	18424 KB	Output is correct
4	Correct	181 ms	18424 KB	Output is correct
5	Correct	182 ms	18424 KB	Output is correct
6	Correct	194 ms	25448 KB	Output is correct
7	Correct	182 ms	22136 KB	Output is correct
8	Correct	222 ms	21240 KB	Output is correct
9	Correct	210 ms	20216 KB	Output is correct
10	Correct	189 ms	18424 KB	Output is correct
11	Correct	199 ms	18428 KB	Output is correct
12	Correct	195 ms	18424 KB	Output is correct
13	Correct	183 ms	18424 KB	Output is correct
14	Correct	157 ms	18040 KB	Output is correct
15	Correct	139 ms	17656 KB	Output is correct
16	Correct	92 ms	15992 KB	Output is correct
17	Correct	120 ms	19680 KB	Output is correct
18	Correct	129 ms	19428 KB	Output is correct
19	Correct	126 ms	19424 KB	Output is correct
20	Correct	126 ms	19296 KB	Output is correct

Subtask #6
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	6016 KB	Output is correct
2	Correct	5 ms	5920 KB	Output is correct
3	Correct	5 ms	5888 KB	Output is correct
4	Correct	6 ms	5888 KB	Output is correct
5	Correct	5 ms	5888 KB	Output is correct
6	Correct	4 ms	5888 KB	Output is correct
7	Correct	5 ms	5888 KB	Output is correct
8	Correct	4 ms	5888 KB	Output is correct
9	Correct	4 ms	5888 KB	Output is correct
10	Correct	4 ms	5888 KB	Output is correct
11	Correct	4 ms	5888 KB	Output is correct
12	Correct	5 ms	6016 KB	Output is correct
13	Correct	5 ms	6016 KB	Output is correct
14	Correct	4 ms	5992 KB	Output is correct
15	Correct	4 ms	6016 KB	Output is correct
16	Correct	5 ms	5888 KB	Output is correct
17	Correct	4 ms	5888 KB	Output is correct
18	Correct	4 ms	5888 KB	Output is correct
19	Correct	5 ms	5888 KB	Output is correct
20	Correct	5 ms	5888 KB	Output is correct
21	Correct	5 ms	6016 KB	Output is correct
22	Correct	4 ms	6016 KB	Output is correct
23	Correct	4 ms	6016 KB	Output is correct
24	Correct	5 ms	6144 KB	Output is correct
25	Correct	4 ms	5888 KB	Output is correct
26	Correct	4 ms	5888 KB	Output is correct
27	Correct	4 ms	5888 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	164 ms	18424 KB	Output is correct
2	Correct	189 ms	18212 KB	Output is correct
3	Correct	136 ms	16248 KB	Output is correct
4	Correct	138 ms	15480 KB	Output is correct
5	Correct	121 ms	14328 KB	Output is correct
6	Correct	109 ms	13816 KB	Output is correct
7	Correct	104 ms	13560 KB	Output is correct
8	Correct	100 ms	13560 KB	Output is correct
9	Correct	111 ms	13304 KB	Output is correct
10	Correct	101 ms	13304 KB	Output is correct
11	Correct	106 ms	13176 KB	Output is correct
12	Correct	108 ms	13432 KB	Output is correct
13	Correct	114 ms	13592 KB	Output is correct
14	Correct	106 ms	16120 KB	Output is correct
15	Correct	164 ms	21372 KB	Output is correct
16	Correct	170 ms	20036 KB	Output is correct
17	Correct	154 ms	20088 KB	Output is correct
18	Correct	149 ms	18808 KB	Output is correct
19	Correct	137 ms	15480 KB	Output is correct
20	Correct	146 ms	15608 KB	Output is correct
21	Correct	122 ms	15608 KB	Output is correct
22	Correct	103 ms	15224 KB	Output is correct
23	Correct	101 ms	14840 KB	Output is correct
24	Correct	125 ms	17524 KB	Output is correct
25	Correct	129 ms	17652 KB	Output is correct
26	Correct	143 ms	16624 KB	Output is correct
27	Correct	149 ms	16376 KB	Output is correct

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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

Submission #260964

Compilation message