Submission #714476

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
714476	2023-03-24T15:27:05 Z	radal	Duathlon (APIO18_duathlon)	C++17	23 / 100	136 ms	28768 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;
bool vis[N];

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;
	vis[v] = 1;
	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 (vis[u]) 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	8 ms	10448 KB	Output is correct
3	Correct	6 ms	10452 KB	Output is correct
4	Correct	6 ms	10452 KB	Output is correct
5	Correct	6 ms	10452 KB	Output is correct
6	Correct	6 ms	10452 KB	Output is correct
7	Incorrect	6 ms	10576 KB	Output isn't correct
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	8 ms	10448 KB	Output is correct
3	Correct	6 ms	10452 KB	Output is correct
4	Correct	6 ms	10452 KB	Output is correct
5	Correct	6 ms	10452 KB	Output is correct
6	Correct	6 ms	10452 KB	Output is correct
7	Incorrect	6 ms	10576 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #3
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	136 ms	28768 KB	Output isn't correct
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	10580 KB	Output is correct
3	Correct	6 ms	10580 KB	Output is correct
4	Correct	7 ms	10652 KB	Output is correct
5	Correct	8 ms	10580 KB	Output is correct
6	Correct	7 ms	10648 KB	Output is correct
7	Correct	7 ms	10580 KB	Output is correct
8	Correct	7 ms	10580 KB	Output is correct
9	Correct	7 ms	10516 KB	Output is correct
10	Correct	7 ms	10580 KB	Output is correct
11	Correct	7 ms	10520 KB	Output is correct
12	Correct	7 ms	10580 KB	Output is correct
13	Correct	6 ms	10580 KB	Output is correct
14	Correct	8 ms	10552 KB	Output is correct
15	Correct	7 ms	10580 KB	Output is correct
16	Correct	7 ms	10580 KB	Output is correct
17	Correct	9 ms	10580 KB	Output is correct
18	Correct	6 ms	10580 KB	Output is correct
19	Correct	6 ms	10572 KB	Output is correct
20	Correct	6 ms	10648 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	19080 KB	Output is correct
2	Correct	77 ms	19376 KB	Output is correct
3	Correct	80 ms	19312 KB	Output is correct
4	Correct	88 ms	19364 KB	Output is correct
5	Correct	105 ms	19396 KB	Output is correct
6	Correct	116 ms	27744 KB	Output is correct
7	Correct	88 ms	22364 KB	Output is correct
8	Correct	86 ms	21444 KB	Output is correct
9	Correct	86 ms	20728 KB	Output is correct
10	Correct	77 ms	19156 KB	Output is correct
11	Correct	101 ms	19268 KB	Output is correct
12	Correct	108 ms	19088 KB	Output is correct
13	Correct	71 ms	19096 KB	Output is correct
14	Correct	67 ms	18752 KB	Output is correct
15	Correct	59 ms	18408 KB	Output is correct
16	Correct	70 ms	16236 KB	Output is correct
17	Correct	56 ms	19948 KB	Output is correct
18	Correct	65 ms	19868 KB	Output is correct
19	Correct	52 ms	20056 KB	Output is correct
20	Correct	57 ms	19852 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	6 ms	10580 KB	Output is correct
3	Incorrect	6 ms	10580 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	19136 KB	Output is correct
2	Correct	85 ms	18880 KB	Output is correct
3	Incorrect	97 ms	20092 KB	Output isn't correct
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	8 ms	10448 KB	Output is correct
3	Correct	6 ms	10452 KB	Output is correct
4	Correct	6 ms	10452 KB	Output is correct
5	Correct	6 ms	10452 KB	Output is correct
6	Correct	6 ms	10452 KB	Output is correct
7	Incorrect	6 ms	10576 KB	Output isn't correct
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	8 ms	10448 KB	Output is correct
3	Correct	6 ms	10452 KB	Output is correct
4	Correct	6 ms	10452 KB	Output is correct
5	Correct	6 ms	10452 KB	Output is correct
6	Correct	6 ms	10452 KB	Output is correct
7	Incorrect	6 ms	10576 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Submission #714476

Compilation message