제출 #103648

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103648		zubec	철인 이종 경기 (APIO18_duathlon)	C++14	23 / 100	261 ms	18900 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 100100;

int n, m;

vector <pair<int, int> > g[N];

ll sz[N];

bool used[N], isBridge[200100];

int tin[N], fup[N], tim;

vector <int> vec;

int clr[N], cnt, szCmp[N], pr[N];

vector <int> gg[N];

void findBridges(int v, int p){
    tin[v] = fup[v] = ++tim;
    vec.push_back(v);
    used[v] = 1;
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i].first, id = g[v][i].second;
        if (to == p)
            continue;
        if (!used[to]){
            findBridges(to, v);
            fup[v] = min(fup[v], fup[to]);
        } else {
            fup[v] = min(fup[v], tin[to]);
        }
        if (tin[v] < fup[to]){
            isBridge[id] = 1;
        }
    }
}

ll ans1, ans2, ans3;

void dfs1(int v, int p){
    sz[v] = szCmp[v];
    pr[v] = p;
    for (int i = 0; i < gg[v].size(); i++){
        int to = gg[v][i];
        if (to == p)
            continue;
        dfs1(to, v);
        sz[v] += sz[to];
    }
}
void dfs2(int v, int p, ll n){
    ll cursum = n-sz[v];
    for (int i = 0; i < gg[v].size(); i++){
        int to = gg[v][i];
        if (to == p)
            continue;
        dfs2(to, v, n);
        ans1 += cursum*sz[to];
        cursum += sz[to];
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    //freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    for (int i = 1; i <= n; i++){
        if (used[i])
            continue;
        vec.clear();

        findBridges(i, 0);
        for (int j = 0; j < vec.size(); j++){
            int v = vec[j];
            if (clr[v] != 0)
                continue;
            ++cnt;
            clr[v] = cnt;
            queue <int> q;
            q.push(v);
            while(!q.empty()){
                int v = q.front();
                q.pop();
                ++szCmp[clr[v]];
                for (int i = 0; i < g[v].size(); i++){
                    int to = g[v][i].first, id = g[v][i].second;
                    if (clr[to] != 0 || isBridge[id])
                        continue;
                    clr[to] = clr[v];
                    q.push(to);
                }
            }
            ans3 += (szCmp[clr[v]]*(szCmp[clr[v]]-1)*(szCmp[clr[v]]-2) );
        }
        for (int j = 0; j < vec.size(); j++){
            int v = vec[j];
            for (int l = 0; l < g[v].size(); l++){
                int to = g[v][l].first;
                if (clr[v] != clr[to]){
                    gg[clr[v]].push_back(clr[to]);
                }
            }
        }
        dfs1(clr[vec[0]], 0);
        dfs2(clr[vec[0]], 0, sz[clr[vec[0]]] );

        for (int j = 0; j < vec.size(); j++){
            int v = vec[j];
            ll cursz = sz[clr[vec[0]]]-szCmp[clr[v]];
            for (int l = 0; l < g[v].size(); l++){
                int to = g[v][l].first;
                if (clr[v] != clr[to]){
                    if (pr[clr[v]] == clr[to]){
                        cursz -= (sz[clr[vec[0]]]-sz[clr[v]]);
                    } else {
                        cursz -= sz[clr[to]];
                    }
                }
            }
            ans2 += (szCmp[clr[v]]-1)*cursz;
        }

    }
    ans1 *= 2;
    ans2 *= 2;
    //cout << ans1 << ' ' << ans2 << ' ' << ans3;
    cout << ans1+ans2+ans3;

}

/**

8 6
1 2
2 3
3 4

5 6
6 7
7 8

4 3
1 2
2 3
3 4

4 4
1 2
2 3
3 4
4 2

*/

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

count_triplets.cpp: In function 'void findBridges(int, int)':
count_triplets.cpp:28:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs1(int, int)':
count_triplets.cpp:49:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < gg[v].size(); i++){
                     ~~^~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs2(int, int, ll)':
count_triplets.cpp:59:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < gg[v].size(); i++){
                     ~~^~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:86:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < vec.size(); j++){
                         ~~^~~~~~~~~~~~
count_triplets.cpp:98:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int i = 0; i < g[v].size(); i++){
                                 ~~^~~~~~~~~~~~~
count_triplets.cpp:108:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < vec.size(); j++){
                         ~~^~~~~~~~~~~~
count_triplets.cpp:110:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int l = 0; l < g[v].size(); l++){
                             ~~^~~~~~~~~~~~~
count_triplets.cpp:120:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < vec.size(); j++){
                         ~~^~~~~~~~~~~~
count_triplets.cpp:123:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int l = 0; l < g[v].size(); l++){
                             ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 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