oj.uz

Submission #155485

# Submission time Handle Problem Language Result Execution time Memory
155485 2019-09-28T18:33:25 Z Akashi Duathlon (APIO18_duathlon) C++14
31 / 100
 206 ms 28624 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; d[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);
            d[nod] += d[it];

            low[nod] = min(low[nod], low[it]);
            if(low[it] >= h[nod]){
                ++nrc;
                v2[nod].push_back(nrc + n);
                while(!st.empty() && st.top() != nod){
                    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:40:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:62: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:66: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 9 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 10 ms 7420 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Incorrect 8 ms 7416 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 10 ms 7420 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Incorrect 8 ms 7416 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 98 ms 23316 KB Output is correct
2 Correct 102 ms 23388 KB Output is correct
3 Correct 106 ms 23168 KB Output is correct
4 Correct 106 ms 22788 KB Output is correct
5 Correct 98 ms 19920 KB Output is correct
6 Correct 109 ms 22292 KB Output is correct
7 Correct 115 ms 20572 KB Output is correct
8 Correct 125 ms 21112 KB Output is correct
9 Correct 120 ms 18912 KB Output is correct
10 Correct 113 ms 18936 KB Output is correct
11 Correct 116 ms 16220 KB Output is correct
12 Correct 94 ms 15992 KB Output is correct
13 Correct 88 ms 15992 KB Output is correct
14 Correct 92 ms 15684 KB Output is correct
15 Correct 67 ms 14860 KB Output is correct
16 Correct 68 ms 14752 KB Output is correct
17 Correct 11 ms 8952 KB Output is correct
18 Correct 14 ms 8952 KB Output is correct
19 Correct 13 ms 8952 KB Output is correct
20 Correct 13 ms 8952 KB Output is correct
21 Correct 11 ms 8828 KB Output is correct
22 Correct 13 ms 8828 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7416 KB Output is correct
2 Correct 10 ms 7548 KB Output is correct
3 Correct 11 ms 7548 KB Output is correct
4 Correct 8 ms 7672 KB Output is correct
5 Correct 10 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 7548 KB Output is correct
9 Correct 9 ms 7544 KB Output is correct
10 Correct 10 ms 7424 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 7548 KB Output is correct
14 Correct 8 ms 7416 KB Output is correct
15 Correct 9 ms 7544 KB Output is correct
16 Correct 2 ms 7416 KB Output is correct
17 Correct 9 ms 7416 KB Output is correct
18 Correct 9 ms 7416 KB Output is correct
19 Correct 9 ms 7416 KB Output is correct
20 Correct 9 ms 7416 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 18468 KB Output is correct
2 Correct 130 ms 18556 KB Output is correct
3 Correct 172 ms 18524 KB Output is correct
4 Correct 180 ms 18504 KB Output is correct
5 Correct 174 ms 18396 KB Output is correct
6 Correct 206 ms 28624 KB Output is correct
7 Correct 140 ms 24848 KB Output is correct
8 Correct 129 ms 23160 KB Output is correct
9 Correct 136 ms 21712 KB Output is correct
10 Correct 125 ms 18492 KB Output is correct
11 Correct 165 ms 18628 KB Output is correct
12 Correct 159 ms 18560 KB Output is correct
13 Correct 140 ms 18532 KB Output is correct
14 Correct 102 ms 17912 KB Output is correct
15 Correct 108 ms 17576 KB Output is correct
16 Correct 65 ms 14940 KB Output is correct
17 Correct 74 ms 17520 KB Output is correct
18 Correct 82 ms 17520 KB Output is correct
19 Correct 85 ms 17644 KB Output is correct
20 Correct 89 ms 17528 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 18524 KB Output is correct
2 Correct 127 ms 18680 KB Output is correct
3 Incorrect 142 ms 18232 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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