oj.uz

Submission #1120352

# Submission time Handle Problem Language Result Execution time Memory
1120352 2024-11-28T07:15:30 Z matei__b Duathlon (APIO18_duathlon) C++17
31 / 100
 200 ms 43084 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];

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));

        // 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+=(2*(n-sz[nod])*add);
        ans+=(2*(sz[nod]-sz_comp[nod])*add);

        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]==1)
    {
        ans+=(2ULL*(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);
    }
}

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);
    }

    ll ans1=0;
    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;
            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++)
    {
        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;
}

Compilation message

count_triplets.cpp: In function 'void solve()':
count_triplets.cpp:179:8: warning: unused variable 'ans1' [-Wunused-variable]
  179 |     ll ans1=0;
      |        ^~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10576 KB Output is correct
2 Correct 12 ms 10580 KB Output is correct
3 Correct 11 ms 10564 KB Output is correct
4 Correct 12 ms 10580 KB Output is correct
5 Correct 9 ms 10580 KB Output is correct
6 Correct 10 ms 10580 KB Output is correct
7 Incorrect 8 ms 10580 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 168 ms 39664 KB Output is correct
2 Correct 127 ms 39776 KB Output is correct
3 Correct 162 ms 38760 KB Output is correct
4 Correct 134 ms 39336 KB Output is correct
5 Correct 113 ms 35928 KB Output is correct
6 Correct 168 ms 37708 KB Output is correct
7 Correct 142 ms 36832 KB Output is correct
8 Correct 164 ms 37708 KB Output is correct
9 Correct 144 ms 35948 KB Output is correct
10 Correct 157 ms 35876 KB Output is correct
11 Correct 117 ms 31820 KB Output is correct
12 Correct 133 ms 31760 KB Output is correct
13 Correct 107 ms 31236 KB Output is correct
14 Correct 107 ms 30688 KB Output is correct
15 Correct 84 ms 29188 KB Output is correct
16 Correct 84 ms 28236 KB Output is correct
17 Correct 11 ms 13508 KB Output is correct
18 Correct 12 ms 13396 KB Output is correct
19 Correct 11 ms 13328 KB Output is correct
20 Correct 12 ms 13396 KB Output is correct
21 Correct 12 ms 13408 KB Output is correct
22 Correct 16 ms 13448 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 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 12 ms 10924 KB Output is correct
5 Correct 12 ms 10832 KB Output is correct
6 Correct 12 ms 10832 KB Output is correct
7 Correct 11 ms 10832 KB Output is correct
8 Correct 9 ms 11000 KB Output is correct
9 Correct 13 ms 10832 KB Output is correct
10 Correct 12 ms 10748 KB Output is correct
11 Correct 9 ms 10940 KB Output is correct
12 Correct 10 ms 10740 KB Output is correct
13 Correct 8 ms 10836 KB Output is correct
14 Correct 14 ms 10920 KB Output is correct
15 Correct 10 ms 10920 KB Output is correct
16 Correct 11 ms 10836 KB Output is correct
17 Correct 13 ms 10836 KB Output is correct
18 Correct 9 ms 10836 KB Output is correct
19 Correct 12 ms 10836 KB Output is correct
20 Correct 10 ms 10836 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 38288 KB Output is correct
2 Correct 176 ms 38336 KB Output is correct
3 Correct 200 ms 38312 KB Output is correct
4 Correct 137 ms 38196 KB Output is correct
5 Correct 144 ms 38280 KB Output is correct
6 Correct 162 ms 43084 KB Output is correct
7 Correct 167 ms 41540 KB Output is correct
8 Correct 169 ms 40624 KB Output is correct
9 Correct 164 ms 39752 KB Output is correct
10 Correct 144 ms 38268 KB Output is correct
11 Correct 138 ms 38404 KB Output is correct
12 Correct 141 ms 38240 KB Output is correct
13 Correct 148 ms 38220 KB Output is correct
14 Correct 130 ms 37196 KB Output is correct
15 Correct 138 ms 35972 KB Output is correct
16 Correct 97 ms 30032 KB Output is correct
17 Correct 149 ms 40144 KB Output is correct
18 Correct 181 ms 40140 KB Output is correct
19 Correct 141 ms 39884 KB Output is correct
20 Correct 172 ms 39804 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10832 KB Output is correct
2 Correct 11 ms 10960 KB Output is correct
3 Incorrect 9 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 191 ms 38216 KB Output is correct
2 Correct 128 ms 38216 KB Output is correct
3 Incorrect 152 ms 34800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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