제출 #62280

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62280		Benq	철인 이종 경기 (APIO18_duathlon)	C++11	66 / 100	451 ms	93000 KiB

count_triplets

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

template<int SZ> struct DSU {
    int par[SZ], sz[SZ];
    DSU() {
        F0R(i,SZ) par[i] = i, sz[i] = 1;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    
    bool unite(int x, int y) { // union-by-rank
    	x = get(x), y = get(y);
    	if (x == y) return 0;
    	if (sz[x] < sz[y]) swap(x,y);
    	sz[x] += sz[y], par[y] = x;
    	return 1;
    }
};

DSU<MX> D;

template<int SZ> struct BCC {
    int N, ti = 0;
    vi adj[SZ];
    int disc[SZ], low[SZ], comp[SZ], par[SZ];
    vector<vpi> fin;
    vpi st;
    vi bad[SZ];
    
    void addEdge(int u, int v) {
        adj[u].pb(v), adj[v].pb(u);
    }
    
    void BCCutil(int u, bool root = 0) {
        disc[u] = low[u] = ti++;
        int child = 0;
        
        for (int i: adj[u]) if (i != par[u]) {
            if (disc[i] == -1) {
                child ++; par[i] = u; 
                BCCutil(i);
                low[u] = min(low[u],low[i]);
                
                if (disc[u] < low[i]) { // bridge
                    bad[u].pb(i), bad[i].pb(u);
                } else D.unite(i,u);
            } else if (disc[i] < disc[u]) {
                low[u] = min(low[u],disc[i]);
            }
        }
    }
    
    void bcc() {
        FOR(i,1,N+1) par[i] = disc[i] = low[i] = -1;
        FOR(i,1,N+1) if (disc[i] == -1) {
            BCCutil(i,1);
            if (sz(st)) fin.pb(st);
            st.clear();
        }
    }
};

int n,m,sz[MX], totsz[MX];
ll ans = 0;
set<pi> adj[MX];
BCC<MX> B;
bool visit[MX];

void dfs1(int x, int y = 0) {
    visit[x] = 1;
    totsz[x] = sz[x];
    for (auto i: adj[x]) if (i.f != x && i.f != y) {
        dfs1(i.f,x);
        totsz[x] += totsz[i.f];
    }
}

void dfs2(int x, int p, int y = 0) {
    ans += (ll)sz[x]*(totsz[p]-1)*(totsz[p]-2);
    
    map<int,vi> m;
    for (auto i: adj[x]) if (i.f != x) {
        ll tmp = 0;
        if (totsz[i.f] > totsz[x]) tmp = totsz[p]-totsz[x];
        else tmp = totsz[i.f];
        m[i.s].pb(tmp);
    }
    for (auto a: m) {
        // for vertex: all separate
        ll tot = 1;
        for (auto x: a.s) {
            ans -= (ll)x*(x-1);
            tot += x;
        }
        ans -= (ll)(sz[x]-1)*tot*(tot-1);
    }
    
    for (auto i: adj[x]) if (i.f != x && i.f != y) {
        dfs2(i.f,p,x);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    F0R(i,m) {
        int a,b; cin >> a >> b;
        B.addEdge(a,b);
    }
    B.N = n;
    B.bcc();
    
    FOR(i,1,n+1) {
        sz[D.get(i)] ++;
        for (int j: B.adj[i]) if (D.get(i) != D.get(j)) {
            adj[D.get(i)].insert({D.get(j),i});
        }
    }
    FOR(i,1,n+1) if (!visit[i]) {
        dfs1(i);
        dfs2(i,i);
    }
    cout << ans;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

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