BOJ 35108 게국지

Table of Contents

📝 문제 정보
#

링크: https://www.acmicpc.net/problem/35108

🧐 관찰 및 접근
#

$N$이 2500이니까 뭔가 제곱로그?까진 돌지 않을까 싶다.
음, 어떻게 잡으면 좋을지 모르겠지만, 저 주어진 게국지 그래프에서 안쪽의 네모중 왼쪽 위부터 반시계방향으로 $1, 2, 3, 4$ 라고 하면, $2, 4$번 정점을 기준으로 카운팅하고싶게 생기긴 했다.
일단 예제 그래프를 그려보자.
![[Drawing 2026-03-07 09.54.26.excalidraw.png]]
- 여기서 저 게국지모양을 찾아야 하는데… $1, 2, 3, 4$를 기7준으로 하면 $1, 2, 4$에 $5, 7, 6$을 붙이거나, $6, 7, 5$를 연결하는 두가지가 있겠다.
어.. 정점을 기준으로 세려고 하니 좀 까다로운거 같기도..? 그러면 간선을 기준으로..?
- 그러면 아무래도 양쪽에 날개가 붙어있는 간선으로 생각하자.
- 크아아아악 이래도 안되는데
일단 두 간선을 골라서 사이클을 고정시키는건 맞는거같다.
- 잉 이러면 걍 포함배제로 되는거 아닌가?
  - 그러면 두 정점에 중복되는 정점, 세 정점에 중복되는 정점 뭐 그런게 필요한거같은데…
    - 비트셋으로 하면 될라나? $O(M^2N/64)$ 정도인거같은데;; 일단 짜보자
좀 빡빡하다. 전처리를 잘 하면 시간 내로 들어간다. Clang이 훨 빠르네. 왜지?

💻 풀이
#

코드 (C++):

void solve(){
    int N, M; cin >> N >> M;
    vector<pii> edges;
    vector<bitset<2500>> con(N);
    rep(i, 0, M){
        int u, v; cin >> u >> v;
        u--; v--;
        edges.push_back({u, v});
        con[u][v] = 1;
        con[v][u] = 1;
    }

    vector<ll> cnt1(N);
    rep(i, 0, N) cnt1[i] = con[i].count();

    vector<vector<bitset<2500>>> con2(N, vector<bitset<2500>>(N));
    rep(i, 0, N) rep(j, i+1, N) con2[i][j] = con2[j][i] = con[i]&con[j];
    vector<vector<ll>> cnt2(N, vector<ll>(N));
    rep(i, 0, N) rep(j, i+1, N) cnt2[i][j] = cnt2[j][i] = con2[i][j].count();
    

    auto calc = [&](int v1, int v2, int v3, int v4) -> ll {
        auto &b1 = con[v1], &b2 = con[v2], &b3 = con[v3];

        ll n1 = cnt1[v1] - (con[v1][v2] + con[v1][v3] + con[v1][v4]);
        ll n2 = cnt1[v2] - (con[v2][v1] + con[v2][v3] + con[v2][v4]);
        ll n3 = cnt1[v3] - (con[v3][v1] + con[v3][v2] + con[v3][v4]);

        ll n12 = cnt2[v1][v2] - (con2[v1][v2][v3] + con2[v1][v2][v4]);
        ll n23 = cnt2[v2][v3] - (con2[v2][v3][v1] + con2[v2][v3][v4]);
        ll n31 = cnt2[v3][v1] - (con2[v3][v1][v2] + con2[v3][v1][v4]);

        bitset<2500> b123 = b1&b2&b3;
        ll n123 = b123.count() - b123[v4];

        return n1*n2*n3 - (n12*n3 + n23*n1 + n31*n2) + 2*n123;
    };

    ll ans = 0;
    rep(i, 0, M) rep(j, i+1, M){
        auto [a, b] = edges[i];
        auto [c, d] = edges[j];
        if(a == c || a == d || b == c || b == d) continue;
        if((!con[a][c] || !con[b][d]) && (!con[a][d] || !con[b][c])) continue;

        ll ret = 0;
        ret += calc(a, b, c, d);
        ret += calc(b, c, d, a);
        ret += calc(c, d, a, b);
        ret += calc(d, a, b, c);

        if(con[a][c] && con[b][d]) ans += ret;
        if(con[a][d] && con[b][c]) ans += ret;
    }
    cout << ans/2;
}

🔒

구현 코드 잠금

아래 쿠팡 링크를 방문하시면 코드가 공개됩니다.
광고 수익이 블로그 운영에 도움이 됩니다 🙏

🛒 쿠팡 방문하고 코드 보기

방문 후 잠금이 자동으로 해제됩니다

📝 문제 정보#

🧐 관찰 및 접근#

💻 풀이#

📝 문제 정보
#

🧐 관찰 및 접근
#

💻 풀이
#