제출 #487146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
487146		Redhood	철인 이종 경기 (APIO18_duathlon)	C++14	5 / 100	1096 ms	19892 KiB

count_triplets

#include<bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) (int)(x).size()
typedef long long ll;
typedef long double ld;
using namespace std;
#define int long long
const int N = (int)1e5 + 10;
const int M = (int)2e5 + 10;
vector < pair < int , int > > edges;
vector < int > g[N], tree[N];
int fup[N], tin[N], T, used[N];
bool bridge[M];
int get(int ide, int v){
    return (edges[ide].fi == v ? edges[ide].se : edges[ide].fi);
}
void dfs(int v, int p){
    fup[v] = tin[v] = T++;
    used[v] = 1;
    for(auto &e : g[v]){
        int to = get(e , v);
        if(!used[to]){
            dfs(to, e);
        }
        if(e != p){
            fup[v] = min(fup[v] , fup[to]);
        }
    }
    if(p != -1){
        if(fup[v] == tin[v]){
            bridge[p] = 1;
        }
    }
}
int sz[N];

void colorit(int v, int clr){
    used[v] = clr;
    sz[clr]++;
    for(auto &e : g[v]){
        int to = get(e , v);
        if(bridge[e]){
            if(used[to] && used[to] != clr){
                tree[used[to]].pb(clr);
                tree[clr].pb(used[to]);
            }
            continue;
        }
        if(!used[to]){
            colorit(to , clr);
        }
    }
}
int h[N];

ll ans3, ans2, ans1;



int dead[N], s[N];
void sizes(int v, int p){
    s[v] = 1;
    for(auto &u : tree[v]){
        if(!dead[u] && u != p){
            sizes(u , v);
            s[v] += s[u];
        }
    }
}
int find_cen(int v , int p, int n){
    for(auto &u : tree[v]){
        if(u != p && !dead[u] && s[u] > n / 2)
            return find_cen(u, v , n);
    }
    return v;
}
void dfs1(int v, int p, int H, vector < int > &layer){
    h[v] = H;
    layer.pb(v);
    for(auto &u : tree[v]){
        if(u == p || dead[u])
            continue;
        dfs1(u , v , H + sz[v], layer);
    }
}
vector < int > now;
int cdused[N];
void decompose(int v){
    now.pb(v);
    dead[v] = 1;
    cdused[v] = 1;
    vector < vector < int > > sons;
    for(auto &u : tree[v]){
        if(!dead[u]){
            vector < int > curlayer;
            dfs1(u , -1, sz[v], curlayer);
            sons.pb(curlayer);
        }
    }
    ll sumSmH = 0, sumS = 0;


    for(int f = 0; f < sz(sons); ++f){
        for(auto &i : sons[f]){
            sumS += sz[i];
            sumSmH += 1ll * sz[i] * h[i];
        }
    }

    for(int f = 0; f < sz(sons); ++f){
        /// delete

        ll curS = 0, curSmH =0;
        for(auto &i : sons[f]){
            curS += sz[i];
            curSmH += 1ll * sz[i] * h[i];
        }


        for(auto &i : sons[f]){
            ans3 += 1ll * sz[i] * (h[i] - sz[v]) * (sumS - curS);
            ans3 += 1ll * sz[i] * (sumSmH - curSmH);

            ans3 += 1ll * sz[i] * sz[v] * (h[i] - sz[v]) * 2;
        }
    }

    for(auto &u : tree[v]){
        if(!dead[u]){
            sizes(u , -1);
            decompose(find_cen(u , -1 , s[u]));
        }
    }
}

int solve(int n){
    fill(used , used + N , 0);
    for(int i = 0; i < n; ++i){
        if(!used[i])
        dfs(i , -1);
    }

    /// find t


    int t = 0;
    fill(used , used + N , 0);
    for(int i = 0 ; i < n; ++i){
        if(!used[i]){
            t++;
            colorit(i , t);
        }
    }

//    /// COMPS
//    for(int i = 0 ; i < n; ++i)
//        cout << used[i] << ' ';
//    cout << endl;
//    cout << " EDGES TREE\n";
//    for(int i = 1;i <= t; ++i){
//        for(auto &u : tree[i])
//            cout << i << ' ' << u << endl;
////        cout << endl;
//    }
//
//    cout << endl;


    for(int j = 1; j <= t; ++j){
        if(cdused[j])
            continue;
        now.clear();
        sizes(j , -1);
        decompose(find_cen(j , -1 , s[j]));

        /// calc ans2 and ans1




        ll ONE = 0, SEC = 0;
        for(int i : now){
            ONE += sz[i];
            SEC += (sz[i] * (sz[i] - 1));
        }

        for(int i : now){
            ans2 += 1ll * ((sz[i]-1)*(sz[i]-2) + (sz[i]-1)) * (ONE - sz[i]) * 2;
            ans1 += 1ll * (1ll * sz[i] * (sz[i] - 1) * (sz[i] - 2));
        }

    }
    cout << ans1 << ' ' << ans2 << ' ' << ans3 << endl;
//    cout << ans1 + ans2 + ans3 << endl;
    return ans1 + ans2 + ans3;
}
int used1[N];
int visited[N];
bool rek(int u, int v , int x, bool have){
    if(u == x && !have){
        return false;
    }
    if(u == x){
        return true;
    }
    if(u == v)
        have = 1;
    for(int e : g[u]){
        int to = get(e , u);
        if(!visited[to]){
            visited[to] = 1;
            bool ans = rek(to , v , x , have);
            if(ans)
                return true;
            visited[to] = 0;
        }
    }
    return false;
}
int brute(int n){
    int answer = 0;
    for(int i = 0 ; i < n; ++i){
        for(int m = 0; m < n; ++m){
            for(int en = 0; en < n; ++en){
                if(i == m || i == en || m == en)
                    continue;
                fill(visited , visited + n , 0);
                visited[i] = 1;
               answer += rek(i , m , en, 0);
                visited[i] = 0;
            }
        }
    }
    return answer;
}

mt19937 rng(1999999999973);
signed main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int n , m;
    bool debug = 0;

    if(!debug){
        cin >> n >> m;


        for(int i = 0 ; i < m; ++i){
            int u , v;
            cin >> u >> v;
            --u , --v;
            edges.pb({u , v});
            g[u].pb(i);
            g[v].pb(i);
        }
        cout << brute(n) << '\n';
    }else{

        while(true){
            int n = 10, m = 15;

            vector < int > num(n * n);
            edges.clear();
            for(int i = 0 ; i < n; ++i)
                g[i].clear();
            iota(all(num) , 0);
            shuffle(all(num) , rng);
            int id = 0;
            for(int i = 0; i < n * n; ++i){
                if(m == 0)
                    break;
                int u = num[i] / n, v = num[i] % n;
                if(u == v)
                    continue;
                m--;
                edges.pb({u,v});
                g[u].pb(id);
                g[v].pb(id);
                id++;
            }

            if(brute(n) == solve(n)){
                cout << "OK\n";
            }else{
                cout << "WRONG\n";
                for(auto &u : edges)
                    cout << u.fi << ' ' << u.se << endl;
                cout << brute(n) << ' ' << solve(n) << endl;
                return 0;
            }
        }

    }
    return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7


1 1 1
100000000 1 1 1
1


11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1


4 3
1 2
2 3
3 4


4 4
1 2
2 3
3 4
4 2


6 4
1 2
2 3
4 5
5 6



9 11
1 2
2 3
1 3
4 5
5 6
6 4
7 8
8 9
9 7
1 4
4 7



10 12
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7
10 1
10 4
10 7
*/

• Subtask 1: 5 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10