제출 #236888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236888		Lucina	철인 이종 경기 (APIO18_duathlon)	C++17	31 / 100	647 ms	38296 KiB

count_triplets

#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
*/

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10