Submission #487833

#	Time	Username	Problem	Language	Result	Execution time	Memory
487833		leaked	Duathlon (APIO18_duathlon)	C++14	0 / 100	299 ms	23064 KiB

count_triplets

#include <bits/stdc++.h>

#define f first
#define s second
#define sz(x) (int)(x).size()
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pw(x) (1LL<<(x))
#define m_p make_pair
#define fast_iati ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;
ll ans=0;
const int N=1e5+12;
struct scc{
    int tin[N],tout[N],tmr=1;
    stack<int>stck;
    vec<int> g[N];
    int cnt=0;
    ll bad=0;
    vec<int> sizes;
    void dfs(int v,int p){
        tin[v]=tmr++;
        stck.push(v);
        cnt++;
        for(auto &z : g[v]){
            if(z==p) continue;
            if(tin[z]){
                umin(tin[v],tin[z]);
//                cout<<"YESS "<<v<<endl;
            }
            else{
                dfs(z,v);
                if(tin[z]>=tin[v]){
                    vec<int> vc;
                    while(stck.top()!=z) vc.pb(stck.top()),stck.pop();
                    vc.pb(z);
                    stck.pop();

                    if(tin[v]==tin[z]) vc.pb(v);
                    sizes.pb(sz(vc));
                    cout<<"SCC "<<endl;
                    for(auto &z : vc)
                        cout<<z+1<<' ';
                    cout<<endl;
                }
                umin(tin[v],tin[z]);
            }
        }
//        stck.push(v);
//        cout<<"PUSH "<<v<<endl;
    }
    ll build(int n){
        fill(tin,tin+N,0);
        ll ans=0;
        for(int i=0;i<n;i++){
            if(!tin[i]){
                dfs(i,i);
                ans+=1ll*cnt*(cnt-1)*(cnt-2)/3;
                vec<int>vc;
                while(sz(stck)) vc.pb(stck.top()),stck.pop();
                sizes.pb(sz(vc));
                for(auto &z : sizes){
                    ans+=1ll*(z)*(z-2)*(z-1);
//                    ans+=1ll*(cnt-z)*(z)*(z-1);
                    ///s,c,f
//                    cout<
                }
                cnt=0;
                sizes.clear();
            }
        }
//        cout<<bad<<endl;
//        assert(bad%2==0);
//        ans-=bad/2;
        return ans;
    }
}_sc;
signed main(){
    fast_iati;
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int v,u;
        cin>>v>>u;--v;--u;
        _sc.g[v].pb(u);
        _sc.g[u].pb(v);
    }
    cout<<_sc.build(n);
//    cout<<
    return 0;
}
/*
4 3
1 2
2 3
3 4

4 4
1 2
2 3
3 4
4 2

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

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

• 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