Submission #413576

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
413576	2021-05-29T00:28:42 Z	ScarletS	Duathlon (APIO18_duathlon)	C++17	66 / 100	101 ms	22216 KB

count_triplets

#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

const int N = 1e5+7;
int g[N], tin[N], low[N], sub[N], t, ct, same[N], tot;
long long ans;
vector<int> e[N];
vector<array<int,2>> bccE[N];
bitset<N> d1, d2;

void dfs1(int c, int p)
{
    d1[c]=1;
    tin[c] = low[c] = ++t;
    for (int i : e[c])
        if (i!=p)
        {
            if (d1[i])
                low[c]=min(low[c],tin[i]);
            else
            {
                dfs1(i,c);
                low[c]=min(low[c],low[i]);
            }
        }
}

void dfs2(int c, int gp)
{
    ++g[gp];
    d2[c]=1;
    for (int i : e[c])
        if (!d2[i])
        {
            if (tin[c]<low[i])
            {
                bccE[gp].push_back({++ct,c});
                bccE[ct].push_back({gp,i});
                dfs2(i,ct);
            }
            else
                dfs2(i,gp);
        }
}

void dfs3(int c, int p)
{
    sub[c]=g[c];
    for (auto i : bccE[c])
        if (i[0]!=p)
        {
            dfs3(i[0],c);
            sub[c]+=sub[i[0]];
        }
}

void dfs4(int c, int p)
{
    //3
    ans+=1LL*g[c]*(g[c]-1)*(g[c]-2);
    int x=0;
    for (auto i : bccE[c])
    {
        if (i[0]!=p)
        {
            dfs4(i[0],c);
            //2 1
            ans+=2LL*sub[i[0]]*(g[c]-1)*(g[c]-1);
            //1 1 1
            ans+=2LL*sub[i[0]]*same[i[1]];
            ans+=2LL*g[c]*sub[i[0]]*(x-same[i[1]]);
            
            same[i[1]]+=sub[i[0]];
            x+=sub[i[0]];
        }
        else
        {
            //2 1
            ans+=2LL*(tot-sub[c])*(g[c]-1)*(g[c]-1);
            //1 1 1
            ans+=2LL*(tot-sub[c])*same[i[1]];
            ans+=2LL*g[c]*(tot-sub[c])*(x-same[i[1]]);

            same[i[1]]+=(tot-sub[c]);
            x+=(tot-sub[c]);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,m,x,y;
    cin>>n>>m;
    while (m--)
    {
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    for (int i=1;i<=n;++i)
        if (!d1[i])
        {
            dfs1(i,0);
            dfs2(i,++ct);
            dfs3(ct,0);
            tot=sub[ct];
            dfs4(ct,0);
        }
    cout<<ans;
    return 0;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4940 KB	Output is correct
2	Correct	4 ms	4940 KB	Output is correct
3	Correct	4 ms	5036 KB	Output is correct
4	Correct	3 ms	5032 KB	Output is correct
5	Correct	3 ms	4940 KB	Output is correct
6	Correct	3 ms	4940 KB	Output is correct
7	Correct	4 ms	5036 KB	Output is correct
8	Incorrect	4 ms	4940 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	4940 KB	Output is correct
2	Correct	4 ms	4940 KB	Output is correct
3	Correct	4 ms	5036 KB	Output is correct
4	Correct	3 ms	5032 KB	Output is correct
5	Correct	3 ms	4940 KB	Output is correct
6	Correct	3 ms	4940 KB	Output is correct
7	Correct	4 ms	5036 KB	Output is correct
8	Incorrect	4 ms	4940 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	76 ms	19536 KB	Output is correct
2	Correct	74 ms	19524 KB	Output is correct
3	Correct	92 ms	17404 KB	Output is correct
4	Correct	80 ms	18536 KB	Output is correct
5	Correct	77 ms	15004 KB	Output is correct
6	Correct	78 ms	17056 KB	Output is correct
7	Correct	77 ms	14728 KB	Output is correct
8	Correct	87 ms	15680 KB	Output is correct
9	Correct	78 ms	13876 KB	Output is correct
10	Correct	72 ms	14320 KB	Output is correct
11	Correct	55 ms	12512 KB	Output is correct
12	Correct	56 ms	12280 KB	Output is correct
13	Correct	48 ms	12440 KB	Output is correct
14	Correct	60 ms	12212 KB	Output is correct
15	Correct	40 ms	11972 KB	Output is correct
16	Correct	39 ms	11668 KB	Output is correct
17	Correct	7 ms	6924 KB	Output is correct
18	Correct	8 ms	6988 KB	Output is correct
19	Correct	7 ms	6988 KB	Output is correct
20	Correct	7 ms	6948 KB	Output is correct
21	Correct	7 ms	6860 KB	Output is correct
22	Correct	8 ms	6900 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5068 KB	Output is correct
2	Correct	4 ms	5068 KB	Output is correct
3	Correct	5 ms	5068 KB	Output is correct
4	Correct	4 ms	5196 KB	Output is correct
5	Correct	4 ms	5156 KB	Output is correct
6	Correct	4 ms	5164 KB	Output is correct
7	Correct	4 ms	5196 KB	Output is correct
8	Correct	4 ms	5068 KB	Output is correct
9	Correct	4 ms	5068 KB	Output is correct
10	Correct	4 ms	5040 KB	Output is correct
11	Correct	4 ms	5068 KB	Output is correct
12	Correct	4 ms	5068 KB	Output is correct
13	Correct	4 ms	5068 KB	Output is correct
14	Correct	4 ms	5140 KB	Output is correct
15	Correct	4 ms	5068 KB	Output is correct
16	Correct	4 ms	5068 KB	Output is correct
17	Correct	5 ms	5072 KB	Output is correct
18	Correct	4 ms	5080 KB	Output is correct
19	Correct	4 ms	5068 KB	Output is correct
20	Correct	4 ms	5168 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	77 ms	15148 KB	Output is correct
2	Correct	78 ms	15104 KB	Output is correct
3	Correct	76 ms	15104 KB	Output is correct
4	Correct	76 ms	15156 KB	Output is correct
5	Correct	83 ms	15172 KB	Output is correct
6	Correct	98 ms	22216 KB	Output is correct
7	Correct	90 ms	18256 KB	Output is correct
8	Correct	90 ms	17404 KB	Output is correct
9	Correct	84 ms	16532 KB	Output is correct
10	Correct	83 ms	15208 KB	Output is correct
11	Correct	80 ms	15128 KB	Output is correct
12	Correct	81 ms	15128 KB	Output is correct
13	Correct	87 ms	15180 KB	Output is correct
14	Correct	71 ms	14780 KB	Output is correct
15	Correct	63 ms	14248 KB	Output is correct
16	Correct	41 ms	12320 KB	Output is correct
17	Correct	51 ms	15668 KB	Output is correct
18	Correct	53 ms	15580 KB	Output is correct
19	Correct	53 ms	15660 KB	Output is correct
20	Correct	63 ms	15680 KB	Output is correct

Subtask #6
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5068 KB	Output is correct
2	Correct	4 ms	5032 KB	Output is correct
3	Correct	4 ms	5068 KB	Output is correct
4	Correct	4 ms	5068 KB	Output is correct
5	Correct	4 ms	5040 KB	Output is correct
6	Correct	4 ms	5068 KB	Output is correct
7	Correct	4 ms	5068 KB	Output is correct
8	Correct	4 ms	5008 KB	Output is correct
9	Correct	4 ms	5036 KB	Output is correct
10	Correct	4 ms	5036 KB	Output is correct
11	Correct	4 ms	5068 KB	Output is correct
12	Correct	4 ms	5068 KB	Output is correct
13	Correct	4 ms	5068 KB	Output is correct
14	Correct	4 ms	5068 KB	Output is correct
15	Correct	4 ms	5032 KB	Output is correct
16	Correct	4 ms	5044 KB	Output is correct
17	Correct	4 ms	5040 KB	Output is correct
18	Correct	4 ms	5068 KB	Output is correct
19	Correct	4 ms	5068 KB	Output is correct
20	Correct	4 ms	5068 KB	Output is correct
21	Correct	4 ms	5068 KB	Output is correct
22	Correct	4 ms	5068 KB	Output is correct
23	Correct	4 ms	5068 KB	Output is correct
24	Correct	4 ms	5068 KB	Output is correct
25	Correct	4 ms	5068 KB	Output is correct
26	Correct	4 ms	5032 KB	Output is correct
27	Correct	4 ms	5068 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	86 ms	15212 KB	Output is correct
2	Correct	85 ms	14988 KB	Output is correct
3	Correct	83 ms	13712 KB	Output is correct
4	Correct	76 ms	12456 KB	Output is correct
5	Correct	70 ms	11592 KB	Output is correct
6	Correct	69 ms	11336 KB	Output is correct
7	Correct	68 ms	11072 KB	Output is correct
8	Correct	74 ms	11040 KB	Output is correct
9	Correct	70 ms	10804 KB	Output is correct
10	Correct	68 ms	10776 KB	Output is correct
11	Correct	60 ms	10748 KB	Output is correct
12	Correct	58 ms	10864 KB	Output is correct
13	Correct	58 ms	10948 KB	Output is correct
14	Correct	64 ms	12740 KB	Output is correct
15	Correct	95 ms	17320 KB	Output is correct
16	Correct	88 ms	16068 KB	Output is correct
17	Correct	88 ms	16280 KB	Output is correct
18	Correct	87 ms	15188 KB	Output is correct
19	Correct	77 ms	12560 KB	Output is correct
20	Correct	101 ms	12872 KB	Output is correct
21	Correct	80 ms	12544 KB	Output is correct
22	Correct	63 ms	12184 KB	Output is correct
23	Correct	56 ms	11716 KB	Output is correct
24	Correct	74 ms	13904 KB	Output is correct
25	Correct	75 ms	14088 KB	Output is correct
26	Correct	74 ms	13296 KB	Output is correct
27	Correct	79 ms	13192 KB	Output is correct

Subtask #8
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4940 KB	Output is correct
2	Correct	4 ms	4940 KB	Output is correct
3	Correct	4 ms	5036 KB	Output is correct
4	Correct	3 ms	5032 KB	Output is correct
5	Correct	3 ms	4940 KB	Output is correct
6	Correct	3 ms	4940 KB	Output is correct
7	Correct	4 ms	5036 KB	Output is correct
8	Incorrect	4 ms	4940 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	4940 KB	Output is correct
2	Correct	4 ms	4940 KB	Output is correct
3	Correct	4 ms	5036 KB	Output is correct
4	Correct	3 ms	5032 KB	Output is correct
5	Correct	3 ms	4940 KB	Output is correct
6	Correct	3 ms	4940 KB	Output is correct
7	Correct	4 ms	5036 KB	Output is correct
8	Incorrect	4 ms	4940 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Submission #413576

Compilation message