Submission #411280

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
411280	2021-05-24T22:22:47 Z	penguinhacker	Duathlon (APIO18_duathlon)	C++14	31 / 100	101 ms	26592 KB

count_triplets

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5;
int n, m, tin[mxN], low[mxN], t, who[mxN], cc;
vector<int> adj1[mxN], adj2[mxN], cmp[mxN];
stack<int> st;
vector<ar<int, 2>> br;
ll n2, sz[mxN], ans, dp[mxN];

void make(int u) {
	while(cmp[cc].empty()||cmp[cc].back()^u) {
		cmp[cc].push_back(st.top());
		who[st.top()]=cc;
		st.pop();
	}
	sz[cc]=cmp[cc].size();
	++cc;
}

void dfs1(int u, int p=-1) {
	tin[u]=low[u]=++t;
	++n2;
	st.push(u);
	for (int v : adj1[u]) {
		if (v==p)
			continue;
		if (!tin[v]) {
			dfs1(v, u);
			low[u]=min(low[u], low[v]);
			if (low[v]>tin[u]) { //bridge
				br.push_back({u, v});
				make(v);
			}
		} else
			low[u]=min(low[u], tin[v]);
	}
}

void dfs2(int u) {
	dp[u]=sz[u];
	for (int v : adj2[u]) {
		dfs2(v);
		dp[u]+=dp[v];
		ans-=dp[v]*sz[u]*(dp[v]-1); // v->u->v
		ans-=2*dp[v]*(sz[u]-1);
		ans-=(n2-dp[v])*sz[v]*(n2-dp[v]-1); // u->v->u
		ans-=2*(n2-dp[v])*(sz[v]-1);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i=0; i<m; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj1[u].push_back(v);
		adj1[v].push_back(u);
	}
	for (int i=0; i<n; ++i) {
		if (tin[i])
			continue;
		dfs1(i);
		make(i);
		while(br.size()) {
			ar<int, 2> a=br.back();
			br.pop_back();
			adj2[who[a[0]]].push_back(who[a[1]]);
		}
		ans+=n2*(n2-1)*(n2-2);
		dfs2(who[i]);
		n2=0;
	}
	cout << ans;
	return 0;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7372 KB	Output is correct
2	Correct	5 ms	7372 KB	Output is correct
3	Correct	5 ms	7372 KB	Output is correct
4	Correct	5 ms	7304 KB	Output is correct
5	Correct	4 ms	7376 KB	Output is correct
6	Correct	5 ms	7376 KB	Output is correct
7	Incorrect	5 ms	7372 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7372 KB	Output is correct
2	Correct	5 ms	7372 KB	Output is correct
3	Correct	5 ms	7372 KB	Output is correct
4	Correct	5 ms	7304 KB	Output is correct
5	Correct	4 ms	7376 KB	Output is correct
6	Correct	5 ms	7376 KB	Output is correct
7	Incorrect	5 ms	7372 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	63 ms	23332 KB	Output is correct
2	Correct	62 ms	23252 KB	Output is correct
3	Correct	85 ms	22088 KB	Output is correct
4	Correct	73 ms	23208 KB	Output is correct
5	Correct	65 ms	19132 KB	Output is correct
6	Correct	72 ms	20996 KB	Output is correct
7	Correct	82 ms	19956 KB	Output is correct
8	Correct	79 ms	20932 KB	Output is correct
9	Correct	69 ms	18804 KB	Output is correct
10	Correct	70 ms	18948 KB	Output is correct
11	Correct	67 ms	16836 KB	Output is correct
12	Correct	74 ms	16708 KB	Output is correct
13	Correct	60 ms	16916 KB	Output is correct
14	Correct	56 ms	16712 KB	Output is correct
15	Correct	50 ms	16708 KB	Output is correct
16	Correct	63 ms	16428 KB	Output is correct
17	Correct	14 ms	13252 KB	Output is correct
18	Correct	14 ms	13220 KB	Output is correct
19	Correct	14 ms	13176 KB	Output is correct
20	Correct	14 ms	13132 KB	Output is correct
21	Correct	14 ms	13172 KB	Output is correct
22	Correct	14 ms	13140 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7500 KB	Output is correct
2	Correct	6 ms	7500 KB	Output is correct
3	Correct	6 ms	7396 KB	Output is correct
4	Correct	5 ms	7500 KB	Output is correct
5	Correct	7 ms	7500 KB	Output is correct
6	Correct	5 ms	7500 KB	Output is correct
7	Correct	6 ms	7476 KB	Output is correct
8	Correct	6 ms	7500 KB	Output is correct
9	Correct	5 ms	7500 KB	Output is correct
10	Correct	5 ms	7500 KB	Output is correct
11	Correct	5 ms	7416 KB	Output is correct
12	Correct	5 ms	7500 KB	Output is correct
13	Correct	5 ms	7500 KB	Output is correct
14	Correct	5 ms	7500 KB	Output is correct
15	Correct	5 ms	7508 KB	Output is correct
16	Correct	5 ms	7372 KB	Output is correct
17	Correct	5 ms	7508 KB	Output is correct
18	Correct	5 ms	7504 KB	Output is correct
19	Correct	5 ms	7500 KB	Output is correct
20	Correct	5 ms	7512 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	77 ms	20124 KB	Output is correct
2	Correct	79 ms	20016 KB	Output is correct
3	Correct	100 ms	19996 KB	Output is correct
4	Correct	72 ms	20020 KB	Output is correct
5	Correct	79 ms	20112 KB	Output is correct
6	Correct	90 ms	26592 KB	Output is correct
7	Correct	97 ms	24136 KB	Output is correct
8	Correct	85 ms	23132 KB	Output is correct
9	Correct	80 ms	22180 KB	Output is correct
10	Correct	84 ms	19856 KB	Output is correct
11	Correct	94 ms	19912 KB	Output is correct
12	Correct	75 ms	19520 KB	Output is correct
13	Correct	75 ms	19540 KB	Output is correct
14	Correct	72 ms	19052 KB	Output is correct
15	Correct	76 ms	18776 KB	Output is correct
16	Correct	48 ms	17424 KB	Output is correct
17	Correct	51 ms	19576 KB	Output is correct
18	Correct	57 ms	19384 KB	Output is correct
19	Correct	74 ms	19440 KB	Output is correct
20	Correct	56 ms	19316 KB	Output is correct

Subtask #6
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7500 KB	Output is correct
2	Correct	5 ms	7508 KB	Output is correct
3	Incorrect	5 ms	7500 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	20032 KB	Output is correct
2	Correct	86 ms	20328 KB	Output is correct
3	Incorrect	101 ms	18060 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7372 KB	Output is correct
2	Correct	5 ms	7372 KB	Output is correct
3	Correct	5 ms	7372 KB	Output is correct
4	Correct	5 ms	7304 KB	Output is correct
5	Correct	4 ms	7376 KB	Output is correct
6	Correct	5 ms	7376 KB	Output is correct
7	Incorrect	5 ms	7372 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7372 KB	Output is correct
2	Correct	5 ms	7372 KB	Output is correct
3	Correct	5 ms	7372 KB	Output is correct
4	Correct	5 ms	7304 KB	Output is correct
5	Correct	4 ms	7376 KB	Output is correct
6	Correct	5 ms	7376 KB	Output is correct
7	Incorrect	5 ms	7372 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Submission #411280

Compilation message