oj.uz

Submission #115867

# Submission time Handle Problem Language Result Execution time Memory
115867 2019-06-09T11:56:08 Z zubec Duathlon (APIO18_duathlon) C++14
23 / 100
 225 ms 26904 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 200100;

vector <int> g[N];

vector <int> stck;

vector <vector <int> > cmp;

int tin[N], fup[N], tim, n;

bool used[N];

void findCutpoints(int v, int p){
    used[v] = 1;
    tin[v] = fup[v] = ++tim;
    stck.push_back(v);
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i];
        if (to == p)
            continue;
        if (!used[to]){
            findCutpoints(to, v);
            fup[v] = min(fup[v], fup[to]);
            if (tin[v] <= fup[to]){
                cmp.push_back({v});
                while(cmp.back().back() != to){
                    cmp.back().push_back(stck.back());
                    stck.pop_back();
                }
            }
        } else {
            fup[v] = min(fup[v], tin[to]);
        }
    }
}

ll ans = 0;

int sz[N];

void dfs1(int v, int p){
    sz[v] = v <= n;
    used[v] = 1;
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i];
        if (to == p)
            continue;
        dfs1(to, v);
        sz[v] += sz[to];
    }
}

void dfs2(int v, int p, ll m){
    if (v <= n){
    } else {
        for (int i = 0; i < g[v].size(); i++){
            int to = g[v][i];
            if (to == p)
                ans -= sz[v]*1ll*(sz[v]-1)*((ll)cmp[v-n-1].size()-1); else
                ans -= (m-sz[to])*1ll*(m-sz[to]-1)*((ll)cmp[v-n-1].size()-1);
        }
    }
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i];
        if (to == p)
            continue;
        dfs2(to, v, m);
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++){
        if (!used[i]){
            findCutpoints(i, 0);
            if (!stck.empty()){
                cmp.push_back(stck);
                stck.clear();
            }
        }
    }
    memset(used, 0, sizeof(used));
    for (int i = 1; i <= n; i++)
        g[i].clear();
    for (int i = 0; i < cmp.size(); i++){
        for (int j = 0; j < cmp[i].size(); j++){
            int v = cmp[i][j];
            g[v].push_back(n+i+1);
            g[n+i+1].push_back(v);
        }
    }
    for (int i = 1; i <= n; i++){
        if (!used[i]){
            dfs1(i, 0);
            ans += (sz[i])*1ll*(sz[i]-1)*(sz[i]-2);
            dfs2(i, 0, sz[i]);
        }
    }

    cout << ans;

}

Compilation message

count_triplets.cpp: In function 'void findCutpoints(int, int)':
count_triplets.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs1(int, int)':
count_triplets.cpp:49:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs2(int, int, ll)':
count_triplets.cpp:61:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[v].size(); i++){
                         ~~^~~~~~~~~~~~~
count_triplets.cpp:68:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:99:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < cmp.size(); i++){
                     ~~^~~~~~~~~~~~
count_triplets.cpp:100:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < cmp[i].size(); j++){
                         ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 21680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 19916 KB Output is correct
2 Correct 196 ms 19924 KB Output is correct
3 Correct 175 ms 19876 KB Output is correct
4 Correct 171 ms 20024 KB Output is correct
5 Correct 183 ms 19880 KB Output is correct
6 Correct 225 ms 26904 KB Output is correct
7 Correct 212 ms 24484 KB Output is correct
8 Correct 202 ms 23268 KB Output is correct
9 Correct 199 ms 22180 KB Output is correct
10 Correct 177 ms 19876 KB Output is correct
11 Correct 189 ms 19972 KB Output is correct
12 Correct 167 ms 20036 KB Output is correct
13 Correct 168 ms 20000 KB Output is correct
14 Correct 153 ms 19748 KB Output is correct
15 Correct 128 ms 19576 KB Output is correct
16 Correct 111 ms 19176 KB Output is correct
17 Correct 131 ms 20196 KB Output is correct
18 Correct 122 ms 20252 KB Output is correct
19 Correct 131 ms 20260 KB Output is correct
20 Correct 141 ms 20284 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 20048 KB Output is correct
2 Correct 197 ms 19876 KB Output is correct
3 Incorrect 185 ms 18668 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5376 KB Output isn't correct
2 Halted 0 ms 0 KB -