oj.uz

Submission #236886

# Submission time Handle Problem Language Result Execution time Memory
236886 2020-06-03T16:13:35 Z Lucina Duathlon (APIO18_duathlon) C++17
23 / 100
 243 ms 37340 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);
        }
    }

   // 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 Incorrect 13 ms 14464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 33760 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 14 ms 14592 KB Output is correct
2 Correct 13 ms 14592 KB Output is correct
3 Correct 14 ms 14592 KB Output is correct
4 Correct 13 ms 14720 KB Output is correct
5 Correct 15 ms 14592 KB Output is correct
6 Correct 14 ms 14720 KB Output is correct
7 Correct 14 ms 14720 KB Output is correct
8 Correct 14 ms 14592 KB Output is correct
9 Correct 14 ms 14592 KB Output is correct
10 Correct 14 ms 14592 KB Output is correct
11 Correct 14 ms 14592 KB Output is correct
12 Correct 14 ms 14720 KB Output is correct
13 Correct 14 ms 14592 KB Output is correct
14 Correct 14 ms 14592 KB Output is correct
15 Correct 14 ms 14592 KB Output is correct
16 Correct 13 ms 14592 KB Output is correct
17 Correct 14 ms 14624 KB Output is correct
18 Correct 13 ms 14592 KB Output is correct
19 Correct 14 ms 14592 KB Output is correct
20 Correct 14 ms 14592 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 30320 KB Output is correct
2 Correct 192 ms 30320 KB Output is correct
3 Correct 183 ms 30448 KB Output is correct
4 Correct 193 ms 30288 KB Output is correct
5 Correct 212 ms 30448 KB Output is correct
6 Correct 236 ms 37340 KB Output is correct
7 Correct 243 ms 32796 KB Output is correct
8 Correct 213 ms 32016 KB Output is correct
9 Correct 229 ms 31384 KB Output is correct
10 Correct 197 ms 30320 KB Output is correct
11 Correct 215 ms 30472 KB Output is correct
12 Correct 210 ms 30384 KB Output is correct
13 Correct 183 ms 30320 KB Output is correct
14 Correct 176 ms 29684 KB Output is correct
15 Correct 160 ms 28944 KB Output is correct
16 Correct 100 ms 25636 KB Output is correct
17 Correct 134 ms 31084 KB Output is correct
18 Correct 129 ms 31204 KB Output is correct
19 Correct 138 ms 31324 KB Output is correct
20 Correct 157 ms 31332 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14592 KB Output is correct
2 Correct 14 ms 14592 KB Output is correct
3 Incorrect 15 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 201 ms 30448 KB Output is correct
2 Correct 208 ms 30072 KB Output is correct
3 Incorrect 232 ms 30812 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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