Submission #906691

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
906691	2024-01-14T18:07:43 Z	andrei_boaca	Duathlon (APIO18_duathlon)	C++17	31 / 100	246 ms	37344 KB

count_triplets

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
ll n,m,par[100005],use[100005],niv[100005],nivmin[100005];
map<pii,int> f;
vector<int> muchii[100005];
vector<int> edges[100005];
ll nrcomp;
ll comp[100005],sz[100005],nr[100005],ans;
ll total;
void dfs(int nod)
{
    use[nod]=1;
    nivmin[nod]=niv[nod];
    for(int i:muchii[nod])
    {
        if(i==par[nod])
            continue;
        if(!use[i])
        {
            par[i]=nod;
            niv[i]=niv[nod]+1;
            dfs(i);
            nivmin[nod]=min(nivmin[nod],nivmin[i]);
            if(niv[nod]<nivmin[i])
                f[{nod,i}]=f[{i,nod}]=1;
        }
        else
            nivmin[nod]=min(nivmin[nod],niv[i]);
    }
}
void build(ll nod)
{
    sz[nrcomp]++;
    comp[nod]=nrcomp;
    for(int i:muchii[nod])
        if(comp[i]==0&&f.count({nod,i})==0)
            build(i);
}
void initgo(ll nod)
{
    use[nod]=1;
    total+=sz[nod];
    for(int i:edges[nod])
        if(!use[i])
            initgo(i);
}
void go(ll nod)
{
    nr[nod]=sz[nod];
    vector<ll> vals;
    for(ll i:edges[nod])
        if(i!=par[nod])
        {
            par[i]=nod;
            go(i);
            vals.push_back(nr[i]);
            nr[nod]+=nr[i];
        }
    vals.push_back(total-nr[nod]);
    ll val=sz[nod]*(sz[nod]-1)*(sz[nod]-2);
    ans+=val;
    ll suma=0;
    for(ll i:vals)
    {
        ll a=2LL*sz[nod]*i*suma;
        suma+=i;
        ans+=a;
        a=((sz[nod]-1)*(sz[nod]-2)*i+(sz[nod]-1)*i)*2LL;
        ans+=a;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        muchii[a].push_back(b);
        muchii[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
        if(!use[i])
        {
            niv[i]=1;
            dfs(i);
        }
    for(int i=1;i<=n;i++)
        if(!comp[i])
        {
            nrcomp++;
            build(i);
        }
    for(auto i:f)
    {
        ll a=i.first.first;
        ll b=i.first.second;
        a=comp[a];
        b=comp[b];
        edges[a].push_back(b);
    }
    for(int i=1;i<=n;i++)
    {
        use[i]=0;
        par[i]=0;
    }
    for(int i=1;i<=nrcomp;i++)
        if(!use[i])
        {
            total=0;
            initgo(i);
            go(i);
        }
    cout<<ans;
    return 0;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6492 KB	Output is correct
2	Correct	2 ms	6492 KB	Output is correct
3	Correct	2 ms	6744 KB	Output is correct
4	Correct	2 ms	6492 KB	Output is correct
5	Correct	2 ms	6492 KB	Output is correct
6	Correct	2 ms	6492 KB	Output is correct
7	Incorrect	2 ms	6492 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	6492 KB	Output is correct
2	Correct	2 ms	6492 KB	Output is correct
3	Correct	2 ms	6744 KB	Output is correct
4	Correct	2 ms	6492 KB	Output is correct
5	Correct	2 ms	6492 KB	Output is correct
6	Correct	2 ms	6492 KB	Output is correct
7	Incorrect	2 ms	6492 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	84 ms	24148 KB	Output is correct
2	Correct	52 ms	24156 KB	Output is correct
3	Correct	107 ms	27392 KB	Output is correct
4	Correct	85 ms	26196 KB	Output is correct
5	Correct	132 ms	22984 KB	Output is correct
6	Correct	149 ms	26964 KB	Output is correct
7	Correct	148 ms	26104 KB	Output is correct
8	Correct	151 ms	26884 KB	Output is correct
9	Correct	177 ms	25056 KB	Output is correct
10	Correct	104 ms	24004 KB	Output is correct
11	Correct	80 ms	20700 KB	Output is correct
12	Correct	106 ms	20632 KB	Output is correct
13	Correct	83 ms	20564 KB	Output is correct
14	Correct	67 ms	20056 KB	Output is correct
15	Correct	70 ms	19540 KB	Output is correct
16	Correct	54 ms	19060 KB	Output is correct
17	Correct	7 ms	10588 KB	Output is correct
18	Correct	8 ms	10456 KB	Output is correct
19	Correct	7 ms	10588 KB	Output is correct
20	Correct	7 ms	10424 KB	Output is correct
21	Correct	7 ms	10588 KB	Output is correct
22	Correct	7 ms	10588 KB	Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	221 ms	31284 KB	Output is correct
2	Correct	227 ms	30628 KB	Output is correct
3	Correct	202 ms	30804 KB	Output is correct
4	Correct	174 ms	30700 KB	Output is correct
5	Correct	225 ms	30864 KB	Output is correct
6	Correct	246 ms	37344 KB	Output is correct
7	Correct	186 ms	35408 KB	Output is correct
8	Correct	194 ms	34132 KB	Output is correct
9	Correct	202 ms	33096 KB	Output is correct
10	Correct	201 ms	30860 KB	Output is correct
11	Correct	238 ms	30868 KB	Output is correct
12	Correct	176 ms	30804 KB	Output is correct
13	Correct	208 ms	30700 KB	Output is correct
14	Correct	154 ms	29268 KB	Output is correct
15	Correct	129 ms	27628 KB	Output is correct
16	Correct	92 ms	22180 KB	Output is correct
17	Correct	183 ms	32172 KB	Output is correct
18	Correct	166 ms	32200 KB	Output is correct
19	Correct	194 ms	32280 KB	Output is correct
20	Correct	182 ms	31904 KB	Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	214 ms	30812 KB	Output is correct
2	Correct	191 ms	30728 KB	Output is correct
3	Incorrect	184 ms	25172 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

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

Submission #906691

Compilation message