Submission #714474

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
714474	2023-03-24T15:25:25 Z	radal	Duathlon (APIO18_duathlon)	C++17	23 / 100	1000 ms	1048576 KB

count_triplets

#include <bits/stdc++.h>
//#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O3")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 2e5+20,mod = 998244353;
constexpr ll inf = 1e9+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}

int n,m;
int h[N],mi[N];
bool cut[N];
int mark[N],sz[N],sum[N];
vector<int> G[N],cp,adj[N];
ll ans;

void dfs(int v){
	cp.pb(v);
	mi[v] = h[v];
	int deg = 0;
	for (int u : G[v]){

		if (h[u] != -1){
			mi[v] = min(mi[v],h[u]);
		   	continue;
		}
		deg++;
		h[u] = h[v] + 1;
		dfs(u);
		if (mi[u] >= h[v] && h[v]) cut[v] = 1;
	}
	if (!h[v] && deg > 1) cut[v] = 1;
}

void dfs2(int v,int c){
	if (cut[v]){
		adj[v].pb(c);
		adj[c].pb(v);
		return;
	}
	mark[v] = c;
	sz[c]++;
	for (int u : G[v]){
		if (!mark[u])
			dfs2(u,c);
	}
}

void dfs3(int v,int p){
	sort(all(adj[v]));
	adj[v].resize(unique(all(adj[v]))-adj[v].begin());
	int s;
	if (v > n) s = sz[v];
	else s = 1;
	sum[v] = s;
	if (v > n){
		int x = adj[v].size();
		ans += 1ll*s*(s-1)*(s-2);
		ans += 1ll*x*s*(s-1);
		ans += 2ll*x*(x-1)*s;
		ans += 1ll*x*(x-1)*(x-2);
	}
	for (int u : adj[v]){
		if (u == p) continue;
		dfs3(u,v);
		ans += 1ll*s*sum[u]*(cp.size()-1-sum[u]);
		ans += 1ll*s*(s-1)*sum[u];
		sum[v] += sum[u];
	}

	ans += 1ll*s*(cp.size()-sum[v])*(sum[v]-1);
	ans += 1ll*s*(s-1)*(cp.size()-sum[v]);
}
int main(){
	ios :: sync_with_stdio(0); cin.tie(0);  cout.tie(0);
	memset(h,-1,sizeof h);
	cin >> n >> m;
	rep(i,0,m){
		int u,v;
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
	}
	int cur = n+1;
	rep(i,1,n+1){
		if (h[i] != -1) continue;
		cp.clear();
		h[i] = 0;
		dfs(i);
		if ((int)cp.size() < 3) continue;

		int tedb = 0;
		for (int v : cp){
			if (cut[v]){
				for (int u : G[v]) if (cut[u]) adj[v].pb(u);
				continue;
			}
			if (mark[v]) continue;
			dfs2(v,cur);
			cur++;
			tedb++;
		}
		if (tedb) dfs3(cur-1,-1);
		else dfs3(cp.back(),-1);
	}
	cout << ans << endl;

}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	10452 KB	Output is correct
2	Correct	5 ms	10452 KB	Output is correct
3	Correct	6 ms	10452 KB	Output is correct
4	Correct	7 ms	10464 KB	Output is correct
5	Correct	8 ms	10452 KB	Output is correct
6	Correct	6 ms	10452 KB	Output is correct
7	Runtime error	852 ms	1048576 KB	Execution killed with signal 9
8	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	10452 KB	Output is correct
2	Correct	5 ms	10452 KB	Output is correct
3	Correct	6 ms	10452 KB	Output is correct
4	Correct	7 ms	10464 KB	Output is correct
5	Correct	8 ms	10452 KB	Output is correct
6	Correct	6 ms	10452 KB	Output is correct
7	Runtime error	852 ms	1048576 KB	Execution killed with signal 9
8	Halted	0 ms	0 KB	-

Subtask #3
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1058 ms	1048576 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	10580 KB	Output is correct
2	Correct	7 ms	10508 KB	Output is correct
3	Correct	8 ms	10580 KB	Output is correct
4	Correct	6 ms	10636 KB	Output is correct
5	Correct	6 ms	10664 KB	Output is correct
6	Correct	8 ms	10580 KB	Output is correct
7	Correct	7 ms	10708 KB	Output is correct
8	Correct	6 ms	10580 KB	Output is correct
9	Correct	8 ms	10580 KB	Output is correct
10	Correct	6 ms	10580 KB	Output is correct
11	Correct	7 ms	10580 KB	Output is correct
12	Correct	8 ms	10580 KB	Output is correct
13	Correct	6 ms	10564 KB	Output is correct
14	Correct	7 ms	10512 KB	Output is correct
15	Correct	7 ms	10580 KB	Output is correct
16	Correct	9 ms	10580 KB	Output is correct
17	Correct	9 ms	10580 KB	Output is correct
18	Correct	9 ms	10552 KB	Output is correct
19	Correct	6 ms	10580 KB	Output is correct
20	Correct	7 ms	10532 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	18924 KB	Output is correct
2	Correct	80 ms	20332 KB	Output is correct
3	Correct	96 ms	20288 KB	Output is correct
4	Correct	98 ms	20296 KB	Output is correct
5	Correct	92 ms	20292 KB	Output is correct
6	Correct	121 ms	30240 KB	Output is correct
7	Correct	119 ms	23816 KB	Output is correct
8	Correct	89 ms	22812 KB	Output is correct
9	Correct	116 ms	21904 KB	Output is correct
10	Correct	82 ms	20124 KB	Output is correct
11	Correct	90 ms	20188 KB	Output is correct
12	Correct	109 ms	19976 KB	Output is correct
13	Correct	73 ms	19992 KB	Output is correct
14	Correct	75 ms	19404 KB	Output is correct
15	Correct	68 ms	19032 KB	Output is correct
16	Correct	49 ms	16544 KB	Output is correct
17	Correct	52 ms	20764 KB	Output is correct
18	Correct	54 ms	20672 KB	Output is correct
19	Correct	58 ms	20932 KB	Output is correct
20	Correct	68 ms	20752 KB	Output is correct

Subtask #6
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	10580 KB	Output is correct
2	Correct	7 ms	10580 KB	Output is correct
3	Runtime error	764 ms	1048576 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	81 ms	18964 KB	Output is correct
2	Correct	90 ms	20112 KB	Output is correct
3	Execution timed out	1012 ms	1048576 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	10452 KB	Output is correct
2	Correct	5 ms	10452 KB	Output is correct
3	Correct	6 ms	10452 KB	Output is correct
4	Correct	7 ms	10464 KB	Output is correct
5	Correct	8 ms	10452 KB	Output is correct
6	Correct	6 ms	10452 KB	Output is correct
7	Runtime error	852 ms	1048576 KB	Execution killed with signal 9
8	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	10452 KB	Output is correct
2	Correct	5 ms	10452 KB	Output is correct
3	Correct	6 ms	10452 KB	Output is correct
4	Correct	7 ms	10464 KB	Output is correct
5	Correct	8 ms	10452 KB	Output is correct
6	Correct	6 ms	10452 KB	Output is correct
7	Runtime error	852 ms	1048576 KB	Execution killed with signal 9
8	Halted	0 ms	0 KB	-

Submission #714474

Compilation message