oj.uz

Submission #674358

# Submission time Handle Problem Language Result Execution time Memory
674358 2022-12-23T18:37:57 Z Jarif_Rahman Duathlon (APIO18_duathlon) C++17
31 / 100
 102 ms 33908 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]-X);
    for(int x: tree[nd]) if(x != ss){
        ans+=X*ll(sz[x])*ll(comp_size-sz[x]-X);
    }
    if(bcc_sz[nd] == -1){
        if(ss != -1) ans+=ll(comp_size-sz[nd]-bcc_sz[ss])*X*ll(bcc_sz[ss])*2;
        for(int x: tree[nd]) if(x != ss){
            ans+=X*ll(bcc_sz[x])*(sz[x]-bcc_sz[x])*2;
        }
    }
}


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(auto x: ap) cerr << x << " "; cerr << "ap\n";
    for(int x: bcc) cerr << x << " "; cerr << "bcc\n";
    for(int x: bcc_sz) cerr << x << " "; cerr << "bcc_sz\n";
    for(int i = 0; i < N; i++){
        for(int x: tree[i]) if(x > i) cerr << i << " " << x << "\n";
    }*/

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

        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:129:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     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 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 316 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 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 316 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 71 ms 25548 KB Output is correct
2 Correct 81 ms 25456 KB Output is correct
3 Correct 92 ms 25680 KB Output is correct
4 Correct 73 ms 25452 KB Output is correct
5 Correct 80 ms 22512 KB Output is correct
6 Correct 86 ms 25080 KB Output is correct
7 Correct 90 ms 23388 KB Output is correct
8 Correct 92 ms 23852 KB Output is correct
9 Correct 81 ms 22004 KB Output is correct
10 Correct 81 ms 21600 KB Output is correct
11 Correct 58 ms 16516 KB Output is correct
12 Correct 59 ms 16636 KB Output is correct
13 Correct 52 ms 16148 KB Output is correct
14 Correct 52 ms 16088 KB Output is correct
15 Correct 42 ms 14864 KB Output is correct
16 Correct 40 ms 14720 KB Output is correct
17 Correct 8 ms 9836 KB Output is correct
18 Correct 9 ms 9836 KB Output is correct
19 Correct 8 ms 9832 KB Output is correct
20 Correct 9 ms 9764 KB Output is correct
21 Correct 9 ms 9704 KB Output is correct
22 Correct 9 ms 9828 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 468 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 588 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 584 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 484 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 456 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 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 468 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 88 ms 22524 KB Output is correct
2 Correct 76 ms 22352 KB Output is correct
3 Correct 93 ms 22268 KB Output is correct
4 Correct 81 ms 22268 KB Output is correct
5 Correct 93 ms 22344 KB Output is correct
6 Correct 99 ms 33908 KB Output is correct
7 Correct 102 ms 28628 KB Output is correct
8 Correct 88 ms 26780 KB Output is correct
9 Correct 89 ms 25088 KB Output is correct
10 Correct 81 ms 22340 KB Output is correct
11 Correct 96 ms 22100 KB Output is correct
12 Correct 84 ms 22396 KB Output is correct
13 Correct 84 ms 22280 KB Output is correct
14 Correct 74 ms 22140 KB Output is correct
15 Correct 78 ms 22008 KB Output is correct
16 Correct 42 ms 15356 KB Output is correct
17 Correct 43 ms 17212 KB Output is correct
18 Correct 44 ms 17268 KB Output is correct
19 Correct 48 ms 17368 KB Output is correct
20 Correct 45 ms 17264 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 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 86 ms 22496 KB Output is correct
2 Correct 80 ms 22432 KB Output is correct
3 Incorrect 91 ms 22772 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 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 316 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 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 316 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 -