oj.uz

Submission #235844

# Submission time Handle Problem Language Result Execution time Memory
235844 2020-05-30T07:13:09 Z PeppaPig Duathlon (APIO18_duathlon) C++14
31 / 100
 171 ms 25124 KB 
#include <bits/stdc++.h>

#define long long long

using namespace std;

const int N = 2e5+5;

int n, m;
int pre[N], low[N], c_sz[N];
vector<vector<int> > g(N), bcc;

void tarjan(int u, int p) {
    static int idx = 0;
    static stack<int> S;
    pre[u] = low[u] = ++idx;
    S.emplace(u);
    for(int v : g[u]) if(v != p) {
        if(!pre[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] >= pre[u]) {
                bcc.emplace_back(1, u);
                while(S.top() != u) {
                    bcc.back().emplace_back(S.top());
                    S.pop();
                }
            }
        } else low[u] = min(low[u], pre[v]);
    } 
}

void build_tree() {
    for(int i = 1; i <= n; i++) if(!pre[i])
        tarjan(i, 0);
    g.clear(), g.resize(n + 1);
    for(vector<int> &cc : bcc) {
        c_sz[g.size()] = cc.size();
        g.emplace_back(0);
        for(int u : cc) {
            g[g.size() - 1].emplace_back(u);
            g[u].emplace_back(g.size() - 1);
        }
    }
}

int subsz[N];
long ans;

int get_sz(int u, int p) {
     if(u <= n) subsz[u] = 1;
     for(int v : g[u]) if(v != p)
        subsz[u] += get_sz(v, u);
    return subsz[u];
}

void bad_triplet(int u, int p, int all) {
    if(u <= n) for(int v : g[u]) {
        if(v != p) ans -= 1ll * (c_sz[v] - 1) * (all - subsz[v]) * (all - subsz[v] - 1);
        else ans -= 1ll * (c_sz[v] - 1) * subsz[u] * (subsz[u] - 1);
    }
    for(int v : g[u]) if(v != p)
        bad_triplet(v, u, all);
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1, a, b; i <= m; i++) {
        scanf("%d %d", &a, &b);
        g[a].emplace_back(b), g[b].emplace_back(a);
    }
    build_tree();
    for(int i = 1; i <= n; i++) if(!subsz[i]) {
        get_sz(i, 0);
        ans += 1ll * subsz[i] * (subsz[i] - 1) * (subsz[i] - 2);
        bad_triplet(i, 0, subsz[i]);
    }
    printf("%lld\n", ans);

    return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 7 ms 4992 KB Output is correct
7 Incorrect 7 ms 4992 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 106 ms 19732 KB Output is correct
2 Correct 97 ms 19732 KB Output is correct
3 Correct 131 ms 19560 KB Output is correct
4 Correct 109 ms 19504 KB Output is correct
5 Correct 112 ms 16928 KB Output is correct
6 Correct 123 ms 19240 KB Output is correct
7 Correct 125 ms 18476 KB Output is correct
8 Correct 120 ms 18864 KB Output is correct
9 Correct 129 ms 17580 KB Output is correct
10 Correct 114 ms 17324 KB Output is correct
11 Correct 102 ms 15276 KB Output is correct
12 Correct 110 ms 15156 KB Output is correct
13 Correct 103 ms 14868 KB Output is correct
14 Correct 98 ms 14640 KB Output is correct
15 Correct 70 ms 13484 KB Output is correct
16 Correct 66 ms 13356 KB Output is correct
17 Correct 11 ms 6656 KB Output is correct
18 Correct 10 ms 6656 KB Output is correct
19 Correct 10 ms 6632 KB Output is correct
20 Correct 11 ms 6656 KB Output is correct
21 Correct 10 ms 6656 KB Output is correct
22 Correct 10 ms 6656 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 20140 KB Output is correct
2 Correct 155 ms 20132 KB Output is correct
3 Correct 164 ms 20132 KB Output is correct
4 Correct 156 ms 20144 KB Output is correct
5 Correct 142 ms 20136 KB Output is correct
6 Correct 167 ms 25124 KB Output is correct
7 Correct 158 ms 23464 KB Output is correct
8 Correct 171 ms 22564 KB Output is correct
9 Correct 155 ms 21672 KB Output is correct
10 Correct 137 ms 20132 KB Output is correct
11 Correct 134 ms 20136 KB Output is correct
12 Correct 134 ms 20136 KB Output is correct
13 Correct 135 ms 20104 KB Output is correct
14 Correct 130 ms 18984 KB Output is correct
15 Correct 111 ms 17808 KB Output is correct
16 Correct 70 ms 14124 KB Output is correct
17 Correct 99 ms 20444 KB Output is correct
18 Correct 99 ms 20376 KB Output is correct
19 Correct 109 ms 20492 KB Output is correct
20 Correct 114 ms 20376 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 20136 KB Output is correct
2 Correct 145 ms 20008 KB Output is correct
3 Incorrect 171 ms 18724 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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