oj.uz

Submission #155128

# Submission time Handle Problem Language Result Execution time Memory
155128 2019-09-26T14:25:18 Z Akashi Duathlon (APIO18_duathlon) C++14
31 / 100
 177 ms 35704 KB 
//#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;

int n, m, nrc;
bool viz[100005];
int id[100005], h[100005], low[100005];
vector <int> v[100005];
set <int> v2[100005];
vector <int> ctc[100005];
stack <int> st;

void dfs(int nod, int papa = 0){
    st.push(nod);
    viz[nod] = 1;

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

        if(!viz[it]){
            h[it] = low[it] = h[nod] + 1;
            dfs(it, nod);
            low[nod] = min(low[nod], low[it]);
        }
        else low[nod] = min(low[nod], low[it]);
    }

    if(low[nod] == h[nod]){
        int x;
        ++nrc;
        do{
            x = st.top();
            st.pop();

            id[x] = nrc;
            ctc[nrc].push_back(x);
        }while(x != nod);
    }
}

long long Sol1 = 0;
long long Sol2 = 0;
long long dp[100005][2];

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

    int sz = ctc[nod].size();
    Sol2 = Sol2 + 1LL * sz * 1LL * (sz - 1) * 1LL * (sz - 2);

    dp[nod][0] = sz;
    dp[nod][1] = 1LL * (sz - 1) * (sz - 1);

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

//        Sol1 = Sol1 + 1LL * sz * dp[it][1] + 1LL * (sz - 1) * 1LL * (sz - 1) * 1LL * dp[it][0];
        Sol1 = Sol1 + 1LL * dp[it][1] * dp[nod][0] + 1LL * dp[it][0] * dp[nod][1];

        dp[nod][0] += dp[it][0];
        dp[nod][1] = dp[nod][1] + dp[it][1] + 1LL * sz * dp[it][0];

    }
}

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(viz[i]) continue ;
        dfs(i);
    }

    for(int i = 1; i <= nrc ; ++i){
        for(auto nod : ctc[i]){
            for(auto it : v[nod]){
                if(id[it] != id[nod])
                    v2[i].insert(id[it]);
            }
        }
    }

    memset(viz, 0, sizeof(viz));
    for(int i = 1; i <= nrc ; ++i){
        if(viz[i]) continue ;
        ctc_dfs(i);
    }

    printf("%lld", Sol1 * 2LL + Sol2);

    return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:71: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:75: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 10 ms 9848 KB Output is correct
2 Correct 10 ms 9848 KB Output is correct
3 Correct 11 ms 9848 KB Output is correct
4 Correct 10 ms 9848 KB Output is correct
5 Correct 10 ms 9848 KB Output is correct
6 Correct 10 ms 9848 KB Output is correct
7 Incorrect 10 ms 9852 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Correct 10 ms 9848 KB Output is correct
3 Correct 11 ms 9848 KB Output is correct
4 Correct 10 ms 9848 KB Output is correct
5 Correct 10 ms 9848 KB Output is correct
6 Correct 10 ms 9848 KB Output is correct
7 Incorrect 10 ms 9852 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 93 ms 22832 KB Output is correct
2 Correct 101 ms 22828 KB Output is correct
3 Correct 118 ms 25296 KB Output is correct
4 Correct 113 ms 23904 KB Output is correct
5 Correct 115 ms 21684 KB Output is correct
6 Correct 119 ms 25556 KB Output is correct
7 Correct 129 ms 24312 KB Output is correct
8 Correct 120 ms 25080 KB Output is correct
9 Correct 122 ms 23568 KB Output is correct
10 Correct 114 ms 22844 KB Output is correct
11 Correct 114 ms 20868 KB Output is correct
12 Correct 109 ms 20856 KB Output is correct
13 Correct 123 ms 20912 KB Output is correct
14 Correct 131 ms 20728 KB Output is correct
15 Correct 109 ms 20724 KB Output is correct
16 Correct 76 ms 20348 KB Output is correct
17 Correct 22 ms 15596 KB Output is correct
18 Correct 22 ms 15608 KB Output is correct
19 Correct 22 ms 15608 KB Output is correct
20 Correct 22 ms 15608 KB Output is correct
21 Correct 22 ms 15480 KB Output is correct
22 Correct 24 ms 15452 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10056 KB Output is correct
2 Correct 11 ms 10104 KB Output is correct
3 Correct 11 ms 10104 KB Output is correct
4 Correct 14 ms 10020 KB Output is correct
5 Correct 11 ms 10104 KB Output is correct
6 Correct 11 ms 9976 KB Output is correct
7 Correct 11 ms 10104 KB Output is correct
8 Correct 11 ms 10108 KB Output is correct
9 Correct 11 ms 9976 KB Output is correct
10 Correct 11 ms 10104 KB Output is correct
11 Correct 11 ms 10104 KB Output is correct
12 Correct 11 ms 10104 KB Output is correct
13 Correct 12 ms 10104 KB Output is correct
14 Correct 14 ms 10048 KB Output is correct
15 Correct 11 ms 9976 KB Output is correct
16 Correct 11 ms 9976 KB Output is correct
17 Correct 11 ms 9976 KB Output is correct
18 Correct 11 ms 10104 KB Output is correct
19 Correct 11 ms 10104 KB Output is correct
20 Correct 12 ms 10060 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 28332 KB Output is correct
2 Correct 161 ms 29532 KB Output is correct
3 Correct 148 ms 29592 KB Output is correct
4 Correct 165 ms 29684 KB Output is correct
5 Correct 166 ms 29608 KB Output is correct
6 Correct 170 ms 35704 KB Output is correct
7 Correct 157 ms 32252 KB Output is correct
8 Correct 158 ms 31736 KB Output is correct
9 Correct 160 ms 30920 KB Output is correct
10 Correct 149 ms 29560 KB Output is correct
11 Correct 177 ms 29584 KB Output is correct
12 Correct 149 ms 29728 KB Output is correct
13 Correct 161 ms 29700 KB Output is correct
14 Correct 138 ms 28444 KB Output is correct
15 Correct 128 ms 27256 KB Output is correct
16 Correct 81 ms 23420 KB Output is correct
17 Correct 126 ms 29932 KB Output is correct
18 Correct 135 ms 29840 KB Output is correct
19 Correct 134 ms 29932 KB Output is correct
20 Correct 133 ms 29944 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 28280 KB Output is correct
2 Correct 151 ms 29712 KB Output is correct
3 Incorrect 128 ms 25080 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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