Submission #62296

#	Time	Username	Problem	Language	Result	Execution time	Memory
62296		Benq	Duathlon (APIO18_duathlon)	C++11	100 / 100	497 ms	55052 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;

vi ADJ[2*MX];
int n,m,totsz[2*MX];

void ad(int a, int b) {
    ADJ[a].pb(b), ADJ[b].pb(a);
}

template<int SZ> struct BCC {
    int N, ti = 0;
    vi adj[SZ];
    int disc[SZ], low[SZ], comp[SZ], par[SZ];
    vector<vpi> fin;
    int compsz[SZ];
    vpi st;
    
    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;
                st.pb({u,i});
                BCCutil(i);
                low[u] = min(low[u],low[i]);
                
                if ((root && child > 1) || (!root && disc[u] <= low[i])) { // articulation point!
                    vpi tmp;
                    while (st.back() != mp(u,i)) tmp.pb(st.back()), st.pop_back();
                    tmp.pb(st.back()), st.pop_back();
                    fin.pb(tmp);
                }
            } else if (disc[i] < disc[u]) {
                low[u] = min(low[u],disc[i]);
                st.pb({u,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 co = 0;
        for (auto a: fin) {
            set<int> s;
            for (auto b: a) s.insert(b.f), s.insert(b.s);
            co ++;
            compsz[co] = sz(s);
            for (int i: s) ad(i,n+co);
        }
    }
};

ll ans = 0;
BCC<MX> B;
bool visit[2*MX];

void dfs1(int x, int y = 0) {
    visit[x] = 1; if (x <= n) totsz[x] = 1;
    for (int i: ADJ[x]) if (i != y) {
        dfs1(i,x);
        totsz[x] += totsz[i];
    }
}

void dfs2(int x, int p, int y = 0) {
    if (x <= n) {
        for (int i: ADJ[x]) {
            assert(i > n);
            if (i != y) {
                ans -= (ll)(B.compsz[i-n]-1)*(totsz[p]-totsz[i])*(totsz[p]-totsz[i]-1);
            } else {
                ans -= (ll)(B.compsz[i-n]-1)*totsz[x]*(totsz[x]-1);
            }
        }
    }
    for (int i: ADJ[x]) if (i != y) dfs2(i,p,x);
}

void init() {
    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();
}

void genTree() {
    FOR(i,1,n+1) if (!visit[i]) {
        dfs1(i);
        ans += (ll)totsz[i]*(totsz[i]-1)*(totsz[i]-2);
        // cout << i << " "  << totsz[i] << "\n";
        dfs2(i,i);
    }
}

int main() {
    init();
    genTree();
    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: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 20 / 20
• Subtask 8: 8 / 8
• Subtask 9: 10 / 10