oj.uz

Submission #1120630

# Submission time Handle Problem Language Result Execution time Memory
1120630 2024-11-28T08:25:06 Z matei__b Duathlon (APIO18_duathlon) C++17
31 / 100
 191 ms 45896 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll long long
#define ull unsigned long long
#define ld long double
#define chad char
#define mod 1'000'000'007
#define dim 100005
#define lim 1000000
#define BASE 31
#define NMAX 21'005
#define FOR(i,a,b) for(int i=(a); i<=(b); i++)
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define nr_biti __builtin_popcount
using namespace __gnu_pbds; 
using namespace std;

ifstream fin("b.in");
ofstream fout("b.out");

int t=1;
ll n,m;
vector<int> g[dim];
vector<int> gt[dim];
int low[dim],tin[dim];
bool viz[dim];
int timer;
unordered_map<int,bool> is_bridge[dim];
ll wrong_ones[dim];

void dfs(int nod,int daddy=0)
{
    viz[nod]=1;
    low[nod]=tin[nod]=++timer;

    for(auto it:g[nod])
    {
        if(it==daddy)
            continue;

        if(viz[it])
        {
            low[nod]=min(low[nod],tin[it]);
        }
        else 
        {
            dfs(it,nod);
            low[nod]=min(low[nod],low[it]);

            if(low[it]>tin[nod])
                is_bridge[nod][it]=is_bridge[it][nod]=1;
        }
    }
}

int comp[dim],nr;
ll sz_comp[dim];

void dfs1(int nod)
{
    viz[nod]=1;
    comp[nod]=nr;
    sz_comp[nr]++;

    for(auto it:g[nod])
    {
        if(!viz[it] && !is_bridge[nod][it])
            dfs1(it);
    }
}

ll ans;
ll sz[dim];

void dfs2(int nod,int daddy=0)
{
    viz[nod]=1;
    sz[nod]+=sz_comp[nod];
    for(auto it:gt[nod])
    {
        if(it==daddy)
            continue;

        dfs2(it,nod);
        sz[nod]+=sz[it];
    }

    // nu pot sa iau un nod marginal ca start 

    if(sz_comp[nod]>=3)
    {
        // pot sa aleg toate in aceiasi componenta 
        ans+=(sz_comp[nod]*(sz_comp[nod]-1)*(sz_comp[nod]-2)-wrong_ones[nod]);

        // acum pot sa aleg 2 din aceiasi componenta 
        // sa zicem ca vreau sa merg in sus intai 
        // e clar ca nu pot sa iau nodul de legatura ca start (as trece de 2 ori prin el)

        ll add=(sz_comp[nod]-1)*(sz_comp[nod]-1);
        ans+=(2*(n-sz[nod])*add);

        // daca merg in jos 
        // sa zicem ca am mai multi fii f1,f2,f3,...fk
        // in cazul in care imi aleg un capat in unul din acesti fii e imposibil ca celalalt capat sa fie in nodul de 
        // legatura 

        // sa zicem ca am avea sum (sz_comp[nod]-1)*(sz_comp[nod]-1)*sz[f1] + ... 
        // (sz_comp[nod]-1)*(sz_comp[nod]-1)*(sz[nod]-sz_comp[nod])
        ans+=(2*(sz[nod]-sz_comp[nod])*add);

        // acum sa zicem ca aleg un singur nod din componenta mea 
        // pot sa iau unul de sus si unul de jos 
        // adk (sz[nod]-sz_comp[nod])*(n-sz[nod])*sz_comp[nod]
        // pot sa iau 2 noduri din subarbori diferiti ai fiilor
        // sz[f1]*(sz[nod]-sz_comp[nod]-sz[f1]) + ... 

        ans+=(2*(n-sz[nod])*(sz_comp[nod])*(sz[nod]-sz_comp[nod]));
        for(auto it:gt[nod])
        {
            if(it==daddy)
                continue;
            ans+=(sz[it]*(sz[nod]-sz_comp[nod]-sz[it])*sz_comp[nod]);
        } 
    }
    else if(sz_comp[nod]==2)
    {
        ll add=(sz_comp[nod]-1)*(sz_comp[nod]-1);
        ans+=(2LL*(n-sz[nod])*add);
        ans+=(2LL*(sz[nod]-sz_comp[nod])*add);

        ans+=(2LL*(n-sz[nod])*(sz_comp[nod])*(sz[nod]-sz_comp[nod]));
        for(auto it:gt[nod])
        {
            if(it==daddy)
                continue;
            ans+=(sz[it]*(sz[nod]-sz_comp[nod]-sz[it])*sz_comp[nod]);
        }
    }
    else if(sz_comp[nod]==1)
    {
        ans+=(2LL*(n-sz[nod])*(sz_comp[nod])*(sz[nod]-sz_comp[nod]));
        for(auto it:gt[nod])
        {
            if(it==daddy)
                continue;
            ans+=(sz[it]*(sz[nod]-sz_comp[nod]-sz[it])*sz_comp[nod]);
        }
    }
    
}

ll rep;
void dfs_aux(int nod,int daddy=0)
{
    rep+=sz_comp[nod];
    for(auto it:gt[nod])
    {
        if(it==daddy)
            continue;

        dfs_aux(it,nod);
    }
}

int rep_grupa[dim];
set<int> s;
stack<pii> d;

void pop_until(int u,int v,int c)
{
    s.clear();
    while(d.top().first!=u || d.top().second!=v)
    {
        s.insert(d.top().first);
        s.insert(d.top().second);
        d.pop();
    }
    s.insert(u);
    s.insert(v);
    d.pop();

    ll N=(ll)s.size();
    wrong_ones[c]+=((N)*(N-1)*(sz_comp[c]-N));
}

void dfs_componente(int nod,int daddy,int c)
{
    viz[nod]=1;
    tin[nod]=low[nod]=++timer;

    for(auto it:g[nod])
    {
        if(it==daddy || comp[it]!=c)
            continue;

        if(viz[it])
        {
            low[nod]=min(low[nod],tin[it]);
        }
        else 
        {
            d.push(mp(nod,it));
            dfs_componente(it,nod,c);
            low[nod]=min(low[nod],low[it]);
            if(low[it]>=tin[nod])
                pop_until(nod,it,c);
        }
    }
}

void solve()
{
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }

    for(int i=1; i<=n; i++)
    {
        if(!viz[i])
            dfs(i);
    }

    for(int i=1; i<=n; i++)
        viz[i]=0;

    for(int i=1; i<=n; i++)
    {
        if(!viz[i])
        {
            ++nr;
            rep_grupa[nr]=i;
            dfs1(i);
        }
    }

    for(int i=1; i<=n; i++)
    {
        for(auto it:g[i])
            if(comp[i]!=comp[it])
                gt[comp[i]].pb(comp[it]);
    }

    for(int i=1; i<=n; i++)
        viz[i]=0;

    for(int i=1; i<=nr; i++)
    {
        timer=0;
        dfs_componente(rep_grupa[i],0,i);
    }

    for(int i=1; i<=n; i++)
        viz[i]=0;

    for(int i=1; i<=nr; i++)
    {
        if(!viz[i])
        {
            rep=0;
            dfs_aux(i);
            n=rep;
            dfs2(i);
        }
    }

    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    //cin >> t;
    while(t--)
        solve();

    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10576 KB Output is correct
2 Correct 9 ms 10576 KB Output is correct
3 Correct 9 ms 10576 KB Output is correct
4 Correct 9 ms 10576 KB Output is correct
5 Correct 9 ms 10576 KB Output is correct
6 Correct 7 ms 10576 KB Output is correct
7 Incorrect 8 ms 10524 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 162 ms 45896 KB Output is correct
2 Correct 150 ms 45896 KB Output is correct
3 Correct 171 ms 42268 KB Output is correct
4 Correct 174 ms 44104 KB Output is correct
5 Correct 144 ms 38524 KB Output is correct
6 Correct 143 ms 40204 KB Output is correct
7 Correct 156 ms 38472 KB Output is correct
8 Correct 155 ms 39752 KB Output is correct
9 Correct 145 ms 36936 KB Output is correct
10 Correct 157 ms 37448 KB Output is correct
11 Correct 101 ms 32588 KB Output is correct
12 Correct 114 ms 32328 KB Output is correct
13 Correct 100 ms 32000 KB Output is correct
14 Correct 99 ms 31556 KB Output is correct
15 Correct 76 ms 29976 KB Output is correct
16 Correct 113 ms 29140 KB Output is correct
17 Correct 13 ms 13916 KB Output is correct
18 Correct 13 ms 13904 KB Output is correct
19 Correct 14 ms 13904 KB Output is correct
20 Correct 13 ms 13960 KB Output is correct
21 Correct 13 ms 13828 KB Output is correct
22 Correct 13 ms 13904 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 38728 KB Output is correct
2 Correct 149 ms 38824 KB Output is correct
3 Correct 166 ms 38728 KB Output is correct
4 Correct 154 ms 38728 KB Output is correct
5 Correct 130 ms 38728 KB Output is correct
6 Correct 157 ms 43592 KB Output is correct
7 Correct 132 ms 41976 KB Output is correct
8 Correct 165 ms 41044 KB Output is correct
9 Correct 169 ms 40264 KB Output is correct
10 Correct 142 ms 38728 KB Output is correct
11 Correct 162 ms 38728 KB Output is correct
12 Correct 164 ms 38600 KB Output is correct
13 Correct 142 ms 38792 KB Output is correct
14 Correct 154 ms 37704 KB Output is correct
15 Correct 123 ms 36424 KB Output is correct
16 Correct 90 ms 30536 KB Output is correct
17 Correct 147 ms 40516 KB Output is correct
18 Correct 146 ms 40520 KB Output is correct
19 Correct 141 ms 40332 KB Output is correct
20 Correct 139 ms 40076 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 38576 KB Output is correct
2 Correct 165 ms 38596 KB Output is correct
3 Incorrect 191 ms 35672 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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