oj.uz

Submission #236888

# Submission time Handle Problem Language Result Execution time Memory
236888 2020-06-03T16:20:59 Z Lucina Duathlon (APIO18_duathlon) C++17
31 / 100
 647 ms 38296 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];
vector <int> to_ask[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);
      ///  fprintf(stderr, "subtraction size nod and sub %d %d\n", sz[nod], sub_sz[i]);
    }

    for (int v : to_ask[nod]) {
     //   fprintf(stderr, "nod v %d %d, sz[nod], sub_sz[v] %d %d\n", nod, v, sz[nod], sub_sz[v]);
        ans -= 2LL * (sz[nod] - 1) * sub_sz[v];
    }

    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);
        }
    }
   // fprintf(stderr, "result tree\n");

    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]);
        to_ask[u].push_back(v);
        to_ask[v].push_back(u);
        comp_node.push_back(u);
        comp_node.push_back(v);
    }

    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);
          ///  fprintf(stderr, "pre ans %d\n", ans);
            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, "ANS: here\n");
    printf("%lld\n", ans);

}

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

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:91: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:97: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 13 ms 14464 KB Output is correct
2 Correct 13 ms 14464 KB Output is correct
3 Correct 13 ms 14464 KB Output is correct
4 Correct 12 ms 14464 KB Output is correct
5 Correct 13 ms 14464 KB Output is correct
6 Correct 13 ms 14464 KB Output is correct
7 Incorrect 12 ms 14464 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 13 ms 14464 KB Output is correct
3 Correct 13 ms 14464 KB Output is correct
4 Correct 12 ms 14464 KB Output is correct
5 Correct 13 ms 14464 KB Output is correct
6 Correct 13 ms 14464 KB Output is correct
7 Incorrect 12 ms 14464 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 128 ms 32480 KB Output is correct
2 Correct 120 ms 33912 KB Output is correct
3 Correct 422 ms 33456 KB Output is correct
4 Correct 261 ms 34036 KB Output is correct
5 Correct 302 ms 31216 KB Output is correct
6 Correct 414 ms 34100 KB Output is correct
7 Correct 441 ms 31472 KB Output is correct
8 Correct 455 ms 32752 KB Output is correct
9 Correct 433 ms 30704 KB Output is correct
10 Correct 388 ms 30960 KB Output is correct
11 Correct 292 ms 28656 KB Output is correct
12 Correct 287 ms 28528 KB Output is correct
13 Correct 297 ms 28280 KB Output is correct
14 Correct 276 ms 28148 KB Output is correct
15 Correct 241 ms 26608 KB Output is correct
16 Correct 242 ms 26400 KB Output is correct
17 Correct 17 ms 16896 KB Output is correct
18 Correct 16 ms 16896 KB Output is correct
19 Correct 15 ms 16896 KB Output is correct
20 Correct 16 ms 16896 KB Output is correct
21 Correct 15 ms 16896 KB Output is correct
22 Correct 16 ms 16896 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 31216 KB Output is correct
2 Correct 636 ms 31528 KB Output is correct
3 Correct 637 ms 31216 KB Output is correct
4 Correct 607 ms 31332 KB Output is correct
5 Correct 598 ms 31212 KB Output is correct
6 Correct 615 ms 38296 KB Output is correct
7 Correct 641 ms 33704 KB Output is correct
8 Correct 641 ms 33092 KB Output is correct
9 Correct 647 ms 32152 KB Output is correct
10 Correct 642 ms 31292 KB Output is correct
11 Correct 599 ms 31472 KB Output is correct
12 Correct 610 ms 31216 KB Output is correct
13 Correct 622 ms 31344 KB Output is correct
14 Correct 535 ms 30400 KB Output is correct
15 Correct 498 ms 29660 KB Output is correct
16 Correct 308 ms 26100 KB Output is correct
17 Correct 553 ms 32108 KB Output is correct
18 Correct 572 ms 32172 KB Output is correct
19 Correct 547 ms 32604 KB Output is correct
20 Correct 526 ms 32100 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 31216 KB Output is correct
2 Correct 625 ms 30992 KB Output is correct
3 Incorrect 499 ms 30708 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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