Submission #252413

#	Time	Username	Problem	Language	Result	Execution time	Memory
252413		shayan_p	Duathlon (APIO18_duathlon)	C++14	0 / 100	137 ms	34468 KiB

count_triplets

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 3e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

vector<int> v[maxn], g[maxn], vec;
int up[maxn], h[maxn], val[maxn], n;
bool mark[maxn];
int C;

void add_edge(int a, int b){
    g[a].PB(b);
    g[b].PB(a);
}
void prep(int u){
    n++;
    mark[u] = 1;
    up[u] = h[u];
    for(int y : v[u]){
	if(!mark[y]){
	    int SZ = sz(vec);
	    
	    h[y] = h[u] + 1;
	    prep(y);
	    up[u] = min(up[u], up[y]);
	    
	    if(up[y] == h[u]){
		while(sz(vec) > SZ){
		    add_edge(vec.back(), C);
		    vec.pop_back();
		}
		add_edge(u, C);
		val[C] = sz(g[C]) - 1;
		C++;
	    }
	}
	else{
	    up[u] = min(up[u], h[y]);	    
	}	    
    }    
    vec.PB(u);
}

ll ans;
int SZ[maxn];

void dfs(int u, int par = -1){
    SZ[u] = (u < n);
    ll num = 0;
    for(int y : g[u])
	if(y != par)
	    dfs(y, u), SZ[u]+= SZ[y], num+= 1ll * SZ[y] * (SZ[y]-1);
    num+= 1ll * (n-SZ[u]) * (n-SZ[u]-1);
    ans+= 1ll * val[u] * (1ll * n * (n-1) - num);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int N, m;
    cin >> N >> m;
    for(int i = 0; i < m; i++){
	int a, b;
	cin >> a >> b;
	--a, --b;
	v[a].PB(b);
	v[b].PB(a);
    }
    C = N;
    for(int i = 0; i < N; i++){
	if(!mark[i]){
	    n = 0;
	    prep(i);
	    ans = -1ll * n * (n-1);
	    dfs(i);
	}
    }
    return cout << ans << endl, 0;
}

• 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