Submission #448686

#	Time	Username	Problem	Language	Result	Execution time	Memory
448686		wiwiho	Duathlon (APIO18_duathlon)	C++14	23 / 100	124 ms	36228 KiB

count_triplets

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

/*
 * g: block-cut tree
 * id[v]: vertex in block-cut tree which v belongs to
 * iscut[v]: whether v in origin graph is an articulation
 * bcccut[v]: whether v in block-cut tree is an articulation
 * tg: origin graph
 */

int n;

vector<vector<int>> g;
vector<int> id, sz;
vector<bool> iscut, bcccut;

vector<vector<int>> tg;
vector<int> in, low;
int ts = 1;
stack<int> st;
int bccid = 1;

void init(){
    tg.resize(n + 1);
    in.resize(n + 1);
    low.resize(n + 1);
    id.resize(n + 1, -1);
    g.resize( 2 * n + 1);
    iscut.resize(n + 1);
    bcccut.resize(2 * n + 1);
    sz.resize(2 * n + 1);
}

void addv(int b, int v){
    if(id[v] == -1){
        id[v] = b;
        return;
    }
    if(!iscut[v]){
        int o = id[v];
        iscut[v] = true;
        id[v] = bccid++;
        bcccut[id[v]] = true;
        g[o].eb(id[v]);
        g[id[v]].eb(o);
    }
    g[b].eb(id[v]);
    g[id[v]].eb(b);
}

void dfsbcc(int now, int p){
    in[now] = low[now] = ts++;
    st.push(now);
    int cnt = 0;
    for(int i : tg[now]){
        if(i == p) continue;
        if(in[i]) low[now] = min(low[now], in[i]);
        else{
            cnt++;
            dfsbcc(i, now);
            low[now] = min(low[now], low[i]);

            if(low[i] >= in[now]){
                int nowid = bccid++;
                while(true){
                    int x = st.top();
                    st.pop();
                    addv(nowid, x);
                    if(x == i) break;
                }
                addv(nowid, now);
            }
        }
    }
    if(cnt == 0 && now == p) addv(bccid++, now);
}

vector<ll> dp;

void dfs1(int now, int p){
    dp[now] += sz[now];
    for(int i : g[now]){
        if(i == p) continue;
        dfs1(i, now);
        dp[now] += dp[i];
    }
}

ll ans = 0;
void dfs2(int now, int p, ll total){
    ll tans = 0;
    if(!bcccut[now]){
        ans += sz[now] * (sz[now] - 1) * (sz[now] - 2);
        ll sum = total - sz[now];
        ll tmp = 0;
        for(int i : g[now]){
            ll sub = i == p ? total - dp[now] : dp[i];
            tmp += total - sub;
        }
        for(int i : g[now]){
            ll sub = i == p ? total - dp[now] : dp[i];
            tans += (sum - sub) * sub * sz[now];
            tans += sz[now] * (sz[now] - 1) * sub * 2;

//            tmp -= total - sub;
//            tmp -= sub * ((int)g[now].size() - 1);
//            tans += sub * tmp;
//            tmp += sub * ((int)g[now].size() - 1);
//            tmp += total - sub;
        }
//        cerr << "test " << now << " " << tans << " " << sz[now] << "\n";
        for(int i : g[now]){
            tans += sz[now] * (sz[now] - 1);
            ll sub1 = i == p ? total - dp[now] : dp[i];
            for(int j : g[now]){
                if(i == j) continue;
                ll sub2 = j == p ? total - dp[now] : dp[j];
//                cerr << "sub " << i << " " << j << " " << sub1 << " " << sub2 << " " << total << "\n";
                tans += sub2 * (total - sub1 - sub2) * 2;
            }
        }
    }
    else{
        ll sum = total - 1;
        for(int i : g[now]){
            ll sub = i == p ? total - dp[now] : dp[i];
            tans += (sum - sub) * sub;
        }
    }
//    cerr << "test " << now << " " << tans << "\n";
    ans += tans;
    for(int i : g[now]){
        if(i == p) continue;
        dfs2(i, now, total);
    }
}

int main(){
    StarBurstStream

    int m;
    cin >> n >> m;
    init();
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        tg[u].eb(v);
        tg[v].eb(u);
    }

    for(int i = 1; i <= n; i++){
        if(!in[i]) dfsbcc(i, i);
    }
//    printv(id, cerr);
//    printv(bcccut, cerr);
//    for(int i = 1; i < bccid; i++){
//        cerr << i << ": ";
//        printv(g[i], cerr);
//    }

    for(int i = 1; i <= n; i++){
        sz[id[i]]++;
    }
    dp.resize(2 * n + 1);

    for(int i = 1; i < bccid; i++){
        if(dp[i] != 0) continue;
        dfs1(i, i);
        dfs2(i, i, dp[i]);
    }

    cout << ans << "\n";

    return 0;
}

• 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