oj.uz

Submission #236931

# Submission time Handle Problem Language Result Execution time Memory
236931 2020-06-04T02:48:51 Z Lucina Duathlon (APIO18_duathlon) C++17
18 / 100
 1000 ms 45264 KB 
#include<bits/stdc++.h>
using namespace std;
int const nax = 2e5 + 10;

struct DSU {
    int par[nax];
    int sz[nax];
    int n;

    DSU (int n) {
        this->n = n;
        iota(par + 1, par + 1 + n, 1);
        fill(sz + 1, sz + 1 + n, 1);
    }

    int find (int x) {
        return x == par[x] ? x : par[x] = find(par[x]);
    }

    bool unite (int x, int y) {
        x = find(x), y = find(y);

        if (x == y) return false;

        if (sz[x] < sz[y]) swap(x, y);
        sz[x] += sz[y];
        par[y] = x;

        return true;
    }
};


int n, m;
vector <pair <int, int>> e;
vector <pair <int, int>> a[nax];
vector <int> bridge_id;
int tin[nax], timer, low[nax];
int sz[nax];
vector <int> b[nax];
vector <int> comp_node;
long long ans ;
bool vis[nax];
int sub_sz[nax];
long long all_subtract;
vector <int> important_node[nax];
vector <int> to_convolve[nax];

long long C (long long v) {
    return v * (v - 1) * (v - 2);
}


int dfs_tree_sz (int nod, int from) {
    sub_sz[nod] = sz[nod];
    vis[nod] = true;
    for (int i : b[nod]) {
        if (i != from) {
            sub_sz[nod] += dfs_tree_sz(i, nod);
        }
    }
    return sub_sz[nod];
}

void dfs_triplet (int nod, int from, int tree_sz) {
    for (int i : b[nod]) {
      ///  if (i == from) continue;
        ans -= 1LL * sz[nod] * sub_sz[i] * (sub_sz[i] - 1);
    //    all_subtract += 1LL * sz[nod] * sub_sz[i] * (sub_sz[i] - 1);
        ans -= 2LL * (sz[nod] - 1) * sub_sz[i];
    //    all_subtract += 2LL * (sz[nod] - 1) * sub_sz[i];

    //    fprintf(stderr, "subtract %lld\n", 2LL * (sz[nod] - 1) * sub_sz[i]);
      ///  fprintf(stderr, "subtraction size nod and sub %d %d\n", sz[nod], sub_sz[i]);
    }

    for (int im_nod : important_node[nod]) {
        /**

        */
        long long square_sum = 0;
        long long simple_sum = 0;

        for (int con : to_convolve[im_nod]) {
            square_sum += 1LL * sub_sz[con] * sub_sz[con];
            simple_sum += sub_sz[con];
        }

        long long tot = (simple_sum * simple_sum - square_sum) / 2;
        ans -= tot * (sz[nod] - 1);
    }


    for (int i : b[nod]) {
        if (i != from) {
            int pre_sub_sz_nod = sub_sz[nod];
            int pre_sub_sz_i = sub_sz[i];
            sub_sz[i] = tree_sz;
            sub_sz[nod] = tree_sz - pre_sub_sz_i;
            dfs_triplet(i, nod, tree_sz);
            sub_sz[nod] = pre_sub_sz_nod;
            sub_sz[i] = pre_sub_sz_i;
        }
    }
}



int main () {

    scanf("%d %d", &n, &m);

    e.resize(m);

    int ct = 0;
    for (auto &edge : e) {
        scanf("%d %d", &edge.first, &edge.second);
        a[edge.first].emplace_back(edge.second, ct);
        a[edge.second].emplace_back(edge.first, ct);
        ++ ct;
    }


    DSU ds(n);

    fill(vis + 1, vis + 1 + n, false);

    function <void(int, int)> dfs_scc = [&] (int node, int from_edge) ->void {
        vis[node] = true;
        tin[node] = low[node] = ++ timer;

        for (auto [i, j] : a[node]) {
            if (!vis[i]) {
                dfs_scc(i, j);
                low[node] = min(low[node], low[i]);
                if (low[i] > tin[node]) {
                    bridge_id.push_back(j);
                }
            } else if (j != from_edge) {
            ///    ds.unite(node, i);
                low[node] = min(low[node], tin[i]);
            }
        }
    };


    for (int i = 1 ; i <= n ; ++ i) {
        if (!vis[i]) {
            dfs_scc(i, -1);
        }
    }

    set <int> setik;
    for (int i = 0 ;i < m ; ++ i)
        setik.insert(i);

    for (int i : bridge_id) setik.erase(setik.find(i));
    for (int i : setik) {
        ds.unite(e[i].first, e[i].second);
    }

    for (int i : bridge_id) {
        int u = ds.find(e[i].first);
        int v = ds.find(e[i].second);
        int sz_u = ds.sz[u];
        int sz_v = ds.sz[v];
        sz[u] = sz_u;
        sz[v] = sz_v;
        b[u].push_back(v);
        b[v].push_back(u);

     //   fprintf(stderr, "Edge %d %d\n", u, v);
     //   fprintf(stderr, "%d %d\n", sz[u], sz[v]);
        comp_node.push_back(u);
        comp_node.push_back(v);

        important_node[u].push_back(e[i].first);
        important_node[v].push_back(e[i].second);
        to_convolve[e[i].first].push_back(v);
        to_convolve[e[i].second].push_back(u);
    }

    fill(vis + 1, vis + 1 + n, false);


    for (int i : comp_node) {
        if (!vis[i]) {
            int tree_sz = dfs_tree_sz(i, 0);

            ans += C(tree_sz);
            dfs_triplet(i, 0, tree_sz);
        }
    }

    for (int i = 1 ;i <= n ; ++ i) {
        int comp = ds.find(i);
        if (vis[comp]) continue;
        vis[comp] = true;
        ans += C(ds.sz[comp]);
    }

 //   fprintf(stderr, "all subtract %lld\n",  all_subtract);
    printf("%lld\n", ans);

}

/**
4 3
1 2
2 3
3 4
*/

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:111: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:117:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &edge.first, &edge.second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 38520 KB Output is correct
2 Correct 128 ms 38536 KB Output is correct
3 Correct 209 ms 38568 KB Output is correct
4 Correct 164 ms 39028 KB Output is correct
5 Correct 183 ms 36336 KB Output is correct
6 Correct 205 ms 39276 KB Output is correct
7 Correct 222 ms 36720 KB Output is correct
8 Correct 237 ms 37964 KB Output is correct
9 Correct 219 ms 36080 KB Output is correct
10 Correct 200 ms 36080 KB Output is correct
11 Correct 149 ms 34288 KB Output is correct
12 Correct 148 ms 33908 KB Output is correct
13 Correct 143 ms 33908 KB Output is correct
14 Correct 150 ms 33652 KB Output is correct
15 Correct 127 ms 32496 KB Output is correct
16 Correct 114 ms 31992 KB Output is correct
17 Correct 18 ms 21632 KB Output is correct
18 Correct 18 ms 21632 KB Output is correct
19 Correct 18 ms 21632 KB Output is correct
20 Correct 18 ms 21632 KB Output is correct
21 Correct 18 ms 21632 KB Output is correct
22 Correct 18 ms 21504 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 38356 KB Output is correct
2 Correct 246 ms 38384 KB Output is correct
3 Correct 252 ms 38256 KB Output is correct
4 Correct 233 ms 38256 KB Output is correct
5 Correct 229 ms 38252 KB Output is correct
6 Correct 249 ms 45264 KB Output is correct
7 Correct 265 ms 40604 KB Output is correct
8 Correct 244 ms 39832 KB Output is correct
9 Correct 276 ms 39276 KB Output is correct
10 Correct 235 ms 38256 KB Output is correct
11 Correct 232 ms 38256 KB Output is correct
12 Correct 247 ms 38332 KB Output is correct
13 Correct 238 ms 38384 KB Output is correct
14 Correct 213 ms 37492 KB Output is correct
15 Correct 195 ms 36592 KB Output is correct
16 Correct 125 ms 32624 KB Output is correct
17 Execution timed out 1093 ms 39404 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 38396 KB Output is correct
2 Correct 227 ms 38000 KB Output is correct
3 Incorrect 225 ms 37876 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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