oj.uz

Submission #674291

# Submission time Handle Problem Language Result Execution time Memory
674291 2022-12-23T16:34:22 Z Jarif_Rahman Duathlon (APIO18_duathlon) C++17
31 / 100
 142 ms 33620 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);

    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 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 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 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 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 79 ms 25076 KB Output is correct
2 Correct 86 ms 26136 KB Output is correct
3 Correct 142 ms 26428 KB Output is correct
4 Correct 94 ms 26216 KB Output is correct
5 Correct 83 ms 23196 KB Output is correct
6 Correct 89 ms 25816 KB Output is correct
7 Correct 81 ms 24188 KB Output is correct
8 Correct 102 ms 24836 KB Output is correct
9 Correct 91 ms 22744 KB Output is correct
10 Correct 96 ms 22280 KB Output is correct
11 Correct 71 ms 17112 KB Output is correct
12 Correct 71 ms 17164 KB Output is correct
13 Correct 51 ms 16628 KB Output is correct
14 Correct 67 ms 16576 KB Output is correct
15 Correct 41 ms 15092 KB Output is correct
16 Correct 41 ms 15084 KB Output is correct
17 Correct 9 ms 9836 KB Output is correct
18 Correct 13 ms 9836 KB Output is correct
19 Correct 8 ms 9812 KB Output is correct
20 Correct 9 ms 9788 KB Output is correct
21 Correct 10 ms 9808 KB Output is correct
22 Correct 9 ms 9704 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 456 KB Output is correct
2 Correct 2 ms 456 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 596 KB Output is correct
6 Correct 1 ms 580 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 580 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 2 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 456 KB Output is correct
14 Correct 1 ms 468 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 468 KB Output is correct
18 Correct 1 ms 460 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 98 ms 22012 KB Output is correct
2 Correct 77 ms 22028 KB Output is correct
3 Correct 86 ms 22024 KB Output is correct
4 Correct 77 ms 22040 KB Output is correct
5 Correct 80 ms 21972 KB Output is correct
6 Correct 104 ms 33620 KB Output is correct
7 Correct 96 ms 28496 KB Output is correct
8 Correct 93 ms 26588 KB Output is correct
9 Correct 92 ms 24912 KB Output is correct
10 Correct 96 ms 22060 KB Output is correct
11 Correct 82 ms 22904 KB Output is correct
12 Correct 79 ms 23164 KB Output is correct
13 Correct 82 ms 23028 KB Output is correct
14 Correct 88 ms 22792 KB Output is correct
15 Correct 67 ms 22380 KB Output is correct
16 Correct 41 ms 15484 KB Output is correct
17 Correct 43 ms 17948 KB Output is correct
18 Correct 45 ms 18036 KB Output is correct
19 Correct 45 ms 18140 KB Output is correct
20 Correct 50 ms 17988 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 452 KB Output is correct
2 Correct 1 ms 452 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 82 ms 22020 KB Output is correct
2 Correct 82 ms 22188 KB Output is correct
3 Incorrect 96 ms 23820 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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