oj.uz

Submission #674309

# Submission time Handle Problem Language Result Execution time Memory
674309 2022-12-23T16:52:21 Z Jarif_Rahman Duathlon (APIO18_duathlon) C++17
31 / 100
 136 ms 33576 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int n, m;
vector<vector<int>> graph, tree0;
vector<bool> ap;
vector<int> intime, low;

int N = 0;
vector<vector<int>> tree;
vector<int> bcc, bcc_sz;
vector<int> sz;

ll ans = 0;

int in = 0;
void dfs_ap(int nd, int ss){
    intime[nd] = in++;
    low[nd] = intime[nd];

    for(int x: graph[nd]) if(x != ss){
        if(intime[x] != -1) low[nd] = min(low[nd], intime[x]);
        else{
            tree0[nd].pb(x);
            dfs_ap(x, nd);
            if(low[x] >= intime[nd] && ss != -1) ap[nd] = 1;
            low[nd] = min(low[nd], low[x]);
        }
    }

    if(ss == -1 && tree0[nd].size() > 1) ap[nd] = 1;
}

void dfs_bcc(int nd, int _bcc){
    if(!ap[nd]){
        bcc[nd] = _bcc;
        bcc_sz[_bcc]++;
        for(int x: tree0[nd]) dfs_bcc(x, _bcc);
        return;
    }

    int me = tree.size();
    bcc[nd] = me;
    tree.pb({_bcc});
    bcc_sz.pb(-1);
    tree[_bcc].pb(me);

    for(int x: tree0[nd]){
        if(low[x] >= intime[nd]){
            int __bcc = tree.size();
            tree.pb({me});
            bcc_sz.pb(0);
            tree[me].pb(__bcc);
            dfs_bcc(x, __bcc);
        }
        else dfs_bcc(x, _bcc);
    }
}

void dfs(int nd, int ss){
    sz[nd] = bcc_sz[nd];
    if(sz[nd] == -1) sz[nd] = 1;
    for(int x: tree[nd]) if(x != ss) dfs(x, nd), sz[nd]+=sz[x];
}

int comp_size;
void dfs2(int nd, int ss){
    ll X = bcc_sz[nd];
    if(X == -1) X = 1;
    if(X >= 2) ans+=X*(X-1)*(comp_size-X)*2;

    for(int x: tree[nd]) if(x != ss) dfs2(x, nd);

    ans+=ll(comp_size-sz[nd])*X*ll(sz[nd]-1);
    for(int x: tree[nd]) if(x != ss){
        ans+=X*ll(sz[x])*ll(comp_size-sz[x]-X);
    }
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    graph.resize(n);
    tree0.resize(n);
    ap.resize(n, 0);
    intime.resize(n, -1);
    low.resize(n);
    bcc.resize(n);

    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b; a--, b--;
        graph[a].pb(b);
        graph[b].pb(a);
    }

    for(int i = 0; i < n; i++) if(intime[i] == -1){
        dfs_ap(i, -1);

        tree.pb({});
        bcc_sz.pb(0);
        dfs_bcc(i, int(tree.size())-1);
    }

    N = tree.size();
    sz.resize(N, -1);

    for(int i = 0; i < bcc_sz.size(); i++){
        ll X = bcc_sz[i];
        if(X >= 3) ans+=X*(X-1)*(X-2);
        if(X >= 2){
            for(int x: tree[i]) if(bcc_sz[x] == -1) ans+=X*(X-1);
        }

        if(sz[i] == -1){
            dfs(i, -1);
            comp_size = sz[i];
            dfs2(i, -1);
        }
    }

    cout << ans <<"\n";
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:116:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for(int i = 0; i < bcc_sz.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 320 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 0 ms 212 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 74 ms 25136 KB Output is correct
2 Correct 91 ms 26176 KB Output is correct
3 Correct 101 ms 26372 KB Output is correct
4 Correct 75 ms 26208 KB Output is correct
5 Correct 79 ms 23276 KB Output is correct
6 Correct 94 ms 25776 KB Output is correct
7 Correct 88 ms 24232 KB Output is correct
8 Correct 136 ms 24700 KB Output is correct
9 Correct 80 ms 22748 KB Output is correct
10 Correct 80 ms 22344 KB Output is correct
11 Correct 61 ms 17136 KB Output is correct
12 Correct 57 ms 17148 KB Output is correct
13 Correct 54 ms 16600 KB Output is correct
14 Correct 64 ms 16608 KB Output is correct
15 Correct 52 ms 15008 KB Output is correct
16 Correct 43 ms 14992 KB Output is correct
17 Correct 9 ms 9836 KB Output is correct
18 Correct 9 ms 9836 KB Output is correct
19 Correct 9 ms 9812 KB Output is correct
20 Correct 8 ms 9832 KB Output is correct
21 Correct 8 ms 9808 KB Output is correct
22 Correct 10 ms 9744 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 448 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 584 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 448 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 456 KB Output is correct
18 Correct 1 ms 452 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 22000 KB Output is correct
2 Correct 107 ms 22096 KB Output is correct
3 Correct 83 ms 22008 KB Output is correct
4 Correct 80 ms 21968 KB Output is correct
5 Correct 93 ms 22032 KB Output is correct
6 Correct 126 ms 33576 KB Output is correct
7 Correct 106 ms 28492 KB Output is correct
8 Correct 96 ms 26568 KB Output is correct
9 Correct 88 ms 24824 KB Output is correct
10 Correct 96 ms 22064 KB Output is correct
11 Correct 90 ms 22880 KB Output is correct
12 Correct 82 ms 23148 KB Output is correct
13 Correct 82 ms 23036 KB Output is correct
14 Correct 84 ms 22744 KB Output is correct
15 Correct 72 ms 22384 KB Output is correct
16 Correct 44 ms 15516 KB Output is correct
17 Correct 43 ms 17972 KB Output is correct
18 Correct 44 ms 18004 KB Output is correct
19 Correct 48 ms 18084 KB Output is correct
20 Correct 46 ms 17960 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 22084 KB Output is correct
2 Correct 79 ms 22220 KB Output is correct
3 Incorrect 105 ms 23724 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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