oj.uz

Submission #413571

# Submission time Handle Problem Language Result Execution time Memory
413571 2021-05-29T00:16:15 Z ScarletS Duathlon (APIO18_duathlon) C++17
0 / 100
 605 ms 1048580 KB 
#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]]);
            //cout<<c<<" "<<i[0]<<" "<<sub[i[0]]<<" "<<same[i[1]]<<"\n";
            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]]);
            //cout<<c<<" "<<i[0]<<" "<<(tot-sub[c])<<" "<<same[i[1]]<<"\n";
            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])
        {
            ct=0;
            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 Incorrect 4 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 19500 KB Output is correct
2 Correct 75 ms 19556 KB Output is correct
3 Incorrect 96 ms 17332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
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 4 ms 5068 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5164 KB Output is correct
6 Correct 4 ms 5068 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 5172 KB Output is correct
10 Runtime error 605 ms 1048580 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 15224 KB Output is correct
2 Correct 89 ms 15172 KB Output is correct
3 Correct 83 ms 15116 KB Output is correct
4 Correct 86 ms 15172 KB Output is correct
5 Correct 80 ms 15108 KB Output is correct
6 Correct 100 ms 22252 KB Output is correct
7 Correct 92 ms 18296 KB Output is correct
8 Correct 95 ms 17396 KB Output is correct
9 Correct 86 ms 16604 KB Output is correct
10 Runtime error 602 ms 1048580 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 4 ms 5176 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 5 ms 5068 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 5068 KB Output is correct
9 Correct 4 ms 5040 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 5176 KB Output is correct
13 Correct 4 ms 5028 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Runtime error 508 ms 1048580 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 15136 KB Output is correct
2 Correct 88 ms 15072 KB Output is correct
3 Correct 101 ms 13876 KB Output is correct
4 Correct 83 ms 12740 KB Output is correct
5 Correct 74 ms 11688 KB Output is correct
6 Correct 69 ms 11312 KB Output is correct
7 Correct 69 ms 11080 KB Output is correct
8 Correct 67 ms 10948 KB Output is correct
9 Correct 70 ms 10812 KB Output is correct
10 Correct 64 ms 10780 KB Output is correct
11 Correct 66 ms 10668 KB Output is correct
12 Correct 64 ms 10796 KB Output is correct
13 Correct 63 ms 10856 KB Output is correct
14 Correct 72 ms 12772 KB Output is correct
15 Correct 96 ms 17328 KB Output is correct
16 Correct 93 ms 16196 KB Output is correct
17 Correct 91 ms 16372 KB Output is correct
18 Correct 87 ms 15300 KB Output is correct
19 Runtime error 588 ms 1048580 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -