Submission #859909

#	Time	Username	Problem	Language	Result	Execution time	Memory
859909		c2zi6	Duathlon (APIO18_duathlon)	C++14	0 / 100	92 ms	27332 KiB

count_triplets

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rep(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define repn(i, n) for (int i = 0; i < int(n); ++i)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VPI> VVPI;
template<class T> T setmax(T& a, T& b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T& b) {if (a < b) return a; return a = b;}

const int MAXN = 2e5;   
int n, m;
VVI gp, gp2, comp;
VI stk;
int low[MAXN], num[MAXN], vis[MAXN], ap[MAXN], id[MAXN], cnt[MAXN];
int tc;
int itsz[MAXN];
int N;

void tarjan(int u, int p = -1) {
    vis[u] = 1;
    stk.pb(u);
    num[u] = low[u] = tc++;
    for (int v : gp[u]) {
        if (v == p) continue;
        if (vis[v] == 1) {
            setmin(low[u], num[v]);
        } else if (vis[v] == 0) {
            tarjan(v, u);
            setmin(low[u], low[v]);
            if (low[v] >= num[u]) {
                ap[u] = (num[u] > 0 || num[v] > 1);
                comp.pb(VI{u});
                while (comp.back().back() != v) {
                    comp.back().pb(stk.back());
                    stk.pop_back();
                }
            }
        }
    }
    vis[u] = 2;
}

ll ans = 0;

int dfs(int u, int p = -1) {
    vis[u] = true;
    int ret = 0;
    // cout << "SKSVAV " << u << endl;
    for (int v : gp2[u]) {
        if (v == p) continue;
        int r = dfs(v, u); 
        ret += r - 1;
    }
    // cout << "PRCAV " << u << ", ret = " << ret << endl;
    if (cnt[u] == -1) {
        int retrn = ret + 1;
        // cout << u << " " << retrn << endl;
    // cout << "MYUS@ " << u << " " << retrn << endl;
        return retrn;//ret+1;
    }
    // cout << u+1 << " " << cnt[u] << " " << N << endl;
    ans -= 1ll*cnt[u]*(cnt[u]-1)*(N-cnt[u]);
    // cout << u << " " << cnt[u] << " " << ret << endl;
    ans -= 2ll*cnt[u]*ret*(N-cnt[u]-ret);


    int retrn = cnt[u] + ret;
    // cout << "MYUS@ " << u << " " << retrn << endl;
    return retrn;
}

void solve() {
    cin >> n >> m;
    gp = VVI(n);
    repn(i, m) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        gp[u].pb(v);
        gp[v].pb(u);
    }
    int iter = 0;
    repn(u, n) {
        if (!vis[u]) {
            tc = 0;
            tarjan(u);
            itsz[iter++] = tc;
        }
    }
    int last = 0;
    gp2 = VVI(2*n);
    repn(u, n) if (ap[u]) cnt[last] = -1, id[u] = last++;
    for (VI v : comp) {
        for (int x : v) {
            if (ap[x]) {
                gp2[id[x]].pb(last);
                gp2[last].pb(id[x]);
            } else id[x] = last;
        }
        cnt[last] = v.size();
        last++;
    }
    while (gp2.size() > last) gp2.pop_back();
    n = last;


    fill(vis, vis+n, 0);
    iter = 0;
    repn(u, n) {
        if (!vis[u]) {
            N = itsz[iter];
            ans += N*(N-1)*(N-2);
            // cout << ans << endl;
            dfs(u);
            iter++;
        }
    }
    cout << ans << endl;
}

int main() {
    // ios_base::sync_with_stdio(false);
    // cin.tie(null); cout.tie(null);
    ll t = 1;
    while (t--) solve();
}

Compilation message (stderr)

count_triplets.cpp: In function 'void solve()':
count_triplets.cpp:112:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  112 |     while (gp2.size() > last) gp2.pop_back();
      |            ~~~~~~~~~~~^~~~~~

• Subtask 1: 0 / 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