oj.uz

Submission #155492

# Submission time Handle Problem Language Result Execution time Memory
155492 2019-09-28T18:54:31 Z Akashi Duathlon (APIO18_duathlon) C++14
66 / 100
 193 ms 28424 KB 
//#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;

int n, m, nr, nrc;
bool f[100005], viz[200005], art[100005];
int h[100005], low[100005], d[200005];
vector <int> v[100005];
vector <int> v2[200005];
stack <int> st;
long long Sol;

int dfs(int nod, int papa = 0){
    f[nod] = 1;
    st.push(nod);
    ++nr;

    int cnt = 0;
    for(auto it : v[nod]){
        if(papa == it) continue ;

        if(!f[it]){
            ++cnt;
            h[it] = low[it] = h[nod] + 1;
            dfs(it, nod);

            low[nod] = min(low[nod], low[it]);
            if(low[it] >= h[nod]){
                ++nrc;
                v2[nod].push_back(nrc + n);
                while(v2[nrc + n].empty() || v2[nrc + n].back() != it){
                    v2[nrc + n].push_back(st.top());
                    st.pop();
                }
            }
        }
        else low[nod] = min(low[nod], low[it]);
    }
}

void bdfs(int nod){
    viz[nod] = 1;

    if(nod <= n) d[nod] = 1;

    for(auto it : v2[nod]){
        if(viz[it]) continue ;
        bdfs(it);

        d[nod] += d[it];
        if(nod > n) Sol = Sol - 1LL * v2[nod].size() * d[it] * (d[it] - 1);
    }

    if(nod > n) Sol = Sol - 1LL * (nr - d[nod]) * (nr - d[nod] - 1) * v2[nod].size();
}

int main()
{
//    freopen("1.in", "r", stdin);
//    freopen("1.out", "w", stdout);
    scanf("%d%d", &n, &m);

    int x, y;
    for(int i = 1; i <= m ; ++i){
        scanf("%d%d", &x, &y);

        v[x].push_back(y);
        v[y].push_back(x);
    }

    for(int i = 1; i <= n ; ++i){
        if(f[i]) continue ;
        nr = 0;
        dfs(i);
        Sol = Sol + 1LL * nr * (nr - 1) * (nr - 2);

        if(nr > 2) bdfs(i);
    }

    printf("%lld", Sol);

    return 0;
}

Compilation message

count_triplets.cpp: In function 'int dfs(int, int)':
count_triplets.cpp:39:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:61: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:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7452 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 10 ms 7544 KB Output is correct
9 Correct 10 ms 7416 KB Output is correct
10 Correct 10 ms 7416 KB Output is correct
11 Correct 9 ms 7416 KB Output is correct
12 Correct 10 ms 7416 KB Output is correct
13 Correct 8 ms 7416 KB Output is correct
14 Correct 8 ms 7416 KB Output is correct
15 Correct 8 ms 7416 KB Output is correct
16 Correct 8 ms 7416 KB Output is correct
17 Correct 8 ms 7416 KB Output is correct
18 Correct 8 ms 7416 KB Output is correct
19 Correct 8 ms 7420 KB Output is correct
20 Correct 8 ms 7416 KB Output is correct
21 Correct 8 ms 7416 KB Output is correct
22 Incorrect 9 ms 7388 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7452 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 10 ms 7544 KB Output is correct
9 Correct 10 ms 7416 KB Output is correct
10 Correct 10 ms 7416 KB Output is correct
11 Correct 9 ms 7416 KB Output is correct
12 Correct 10 ms 7416 KB Output is correct
13 Correct 8 ms 7416 KB Output is correct
14 Correct 8 ms 7416 KB Output is correct
15 Correct 8 ms 7416 KB Output is correct
16 Correct 8 ms 7416 KB Output is correct
17 Correct 8 ms 7416 KB Output is correct
18 Correct 8 ms 7416 KB Output is correct
19 Correct 8 ms 7420 KB Output is correct
20 Correct 8 ms 7416 KB Output is correct
21 Correct 8 ms 7416 KB Output is correct
22 Incorrect 9 ms 7388 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 24864 KB Output is correct
2 Correct 103 ms 24912 KB Output is correct
3 Correct 117 ms 23300 KB Output is correct
4 Correct 117 ms 23948 KB Output is correct
5 Correct 105 ms 19808 KB Output is correct
6 Correct 125 ms 22416 KB Output is correct
7 Correct 110 ms 20600 KB Output is correct
8 Correct 116 ms 21060 KB Output is correct
9 Correct 104 ms 18936 KB Output is correct
10 Correct 102 ms 18848 KB Output is correct
11 Correct 84 ms 16252 KB Output is correct
12 Correct 113 ms 16120 KB Output is correct
13 Correct 85 ms 15988 KB Output is correct
14 Correct 79 ms 15740 KB Output is correct
15 Correct 60 ms 14840 KB Output is correct
16 Correct 64 ms 14712 KB Output is correct
17 Correct 12 ms 8568 KB Output is correct
18 Correct 10 ms 8568 KB Output is correct
19 Correct 10 ms 8568 KB Output is correct
20 Correct 12 ms 8568 KB Output is correct
21 Correct 12 ms 8440 KB Output is correct
22 Correct 20 ms 8440 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 18416 KB Output is correct
2 Correct 121 ms 18504 KB Output is correct
3 Correct 113 ms 18524 KB Output is correct
4 Correct 138 ms 18596 KB Output is correct
5 Correct 116 ms 18428 KB Output is correct
6 Correct 149 ms 28424 KB Output is correct
7 Correct 193 ms 24820 KB Output is correct
8 Correct 130 ms 23260 KB Output is correct
9 Correct 130 ms 21724 KB Output is correct
10 Correct 113 ms 18464 KB Output is correct
11 Correct 105 ms 18512 KB Output is correct
12 Correct 111 ms 18680 KB Output is correct
13 Correct 109 ms 18568 KB Output is correct
14 Correct 100 ms 17956 KB Output is correct
15 Correct 92 ms 17452 KB Output is correct
16 Correct 53 ms 14960 KB Output is correct
17 Correct 80 ms 17516 KB Output is correct
18 Correct 82 ms 17604 KB Output is correct
19 Correct 85 ms 17620 KB Output is correct
20 Correct 83 ms 17528 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7420 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 9 ms 7544 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 8 ms 7544 KB Output is correct
8 Correct 9 ms 7416 KB Output is correct
9 Correct 9 ms 7416 KB Output is correct
10 Correct 9 ms 7544 KB Output is correct
11 Correct 9 ms 7544 KB Output is correct
12 Correct 9 ms 7544 KB Output is correct
13 Correct 9 ms 7544 KB Output is correct
14 Correct 9 ms 7548 KB Output is correct
15 Correct 9 ms 7544 KB Output is correct
16 Correct 9 ms 7416 KB Output is correct
17 Correct 9 ms 7544 KB Output is correct
18 Correct 9 ms 7544 KB Output is correct
19 Correct 9 ms 7592 KB Output is correct
20 Correct 9 ms 7420 KB Output is correct
21 Correct 9 ms 7420 KB Output is correct
22 Correct 8 ms 7544 KB Output is correct
23 Correct 9 ms 7416 KB Output is correct
24 Correct 9 ms 7416 KB Output is correct
25 Correct 8 ms 7416 KB Output is correct
26 Correct 9 ms 7420 KB Output is correct
27 Correct 8 ms 7416 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 18424 KB Output is correct
2 Correct 119 ms 18680 KB Output is correct
3 Correct 149 ms 18104 KB Output is correct
4 Correct 125 ms 17016 KB Output is correct
5 Correct 111 ms 15752 KB Output is correct
6 Correct 91 ms 15096 KB Output is correct
7 Correct 84 ms 14844 KB Output is correct
8 Correct 84 ms 14456 KB Output is correct
9 Correct 89 ms 14328 KB Output is correct
10 Correct 83 ms 14200 KB Output is correct
11 Correct 85 ms 14124 KB Output is correct
12 Correct 77 ms 14072 KB Output is correct
13 Correct 115 ms 14200 KB Output is correct
14 Correct 100 ms 16820 KB Output is correct
15 Correct 133 ms 24620 KB Output is correct
16 Correct 168 ms 22264 KB Output is correct
17 Correct 175 ms 22808 KB Output is correct
18 Correct 166 ms 21028 KB Output is correct
19 Correct 138 ms 16976 KB Output is correct
20 Correct 124 ms 16972 KB Output is correct
21 Correct 147 ms 16964 KB Output is correct
22 Correct 144 ms 16500 KB Output is correct
23 Correct 129 ms 15668 KB Output is correct
24 Correct 148 ms 17912 KB Output is correct
25 Correct 145 ms 17836 KB Output is correct
26 Correct 123 ms 17196 KB Output is correct
27 Correct 115 ms 17144 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7452 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 10 ms 7544 KB Output is correct
9 Correct 10 ms 7416 KB Output is correct
10 Correct 10 ms 7416 KB Output is correct
11 Correct 9 ms 7416 KB Output is correct
12 Correct 10 ms 7416 KB Output is correct
13 Correct 8 ms 7416 KB Output is correct
14 Correct 8 ms 7416 KB Output is correct
15 Correct 8 ms 7416 KB Output is correct
16 Correct 8 ms 7416 KB Output is correct
17 Correct 8 ms 7416 KB Output is correct
18 Correct 8 ms 7416 KB Output is correct
19 Correct 8 ms 7420 KB Output is correct
20 Correct 8 ms 7416 KB Output is correct
21 Correct 8 ms 7416 KB Output is correct
22 Incorrect 9 ms 7388 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7452 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 10 ms 7544 KB Output is correct
9 Correct 10 ms 7416 KB Output is correct
10 Correct 10 ms 7416 KB Output is correct
11 Correct 9 ms 7416 KB Output is correct
12 Correct 10 ms 7416 KB Output is correct
13 Correct 8 ms 7416 KB Output is correct
14 Correct 8 ms 7416 KB Output is correct
15 Correct 8 ms 7416 KB Output is correct
16 Correct 8 ms 7416 KB Output is correct
17 Correct 8 ms 7416 KB Output is correct
18 Correct 8 ms 7416 KB Output is correct
19 Correct 8 ms 7420 KB Output is correct
20 Correct 8 ms 7416 KB Output is correct
21 Correct 8 ms 7416 KB Output is correct
22 Incorrect 9 ms 7388 KB Output isn't correct
23 Halted 0 ms 0 KB -