Submission #403755

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
403755	2021-05-13T12:09:49 Z	Bill_00	Duathlon (APIO18_duathlon)	C++14	31 / 100	230 ms	43060 KB

count_triplets

#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define N 100005
using namespace std;
ll n, nn, m, timer, ans;
ll low[N], tin[N], p[N], sz[N], newsz[N], compsz[N];
vector<ll> adj[N], newadj[N];
unordered_map<ll, bool> bridge[N];
bool vis[N], mark[N];
void dfs(ll v, ll p = -1) {
    vis[v] = 1;
    tin[v] = low[v] = timer++;
    for (ll to : adj[v]) {
        if(to == p) continue;
        if(vis[to]){
            low[v] = min(low[v], tin[to]);
        } 
        else{
            dfs(to, v);
            low[v] = min(low[v], low[to]);
            if(low[to] > tin[v]){
            	bridge[v][to]=1;
            	bridge[to][v]=1;
            }
        }
    }
}
void dfs1(ll node, ll head){
	nn++;
	sz[head]++;
	p[node]=head;
	vis[node]=1;
	for(ll to : adj[node]) {
		if(!vis[to]) {
			if(bridge[node][to]) {
				dfs1(to, to);
				newadj[head].pb(to);
				newadj[to].pb(head);
			}
			else dfs1(to, head);
		}
	}
}
void solve(ll node, ll par=-1){
	// cout << node << ' ' << sz[node] << '\n';
	vis[node]=1;
	ll sum=0, res=0;
	ans+=(sz[node]*(sz[node]-1)*(sz[node]-2));
	newsz[node]=sz[node];
	for(ll to : newadj[node]){
		if(par != to) {
			solve(to, node);
			newsz[node]+=newsz[to];
			sum+=newsz[to];
			res+=(newsz[to]*newsz[to]);
			ans+=((sz[node]-1)*(sz[node]-2)*newsz[to]*2+newsz[to]*(sz[node]-1)*2);
		}
	}
	ans+=((sz[node]-1)*(sz[node]-2)*(nn-newsz[node])*2+(nn-newsz[node])*(sz[node]-1)*2);
	ans+=((newsz[node]-sz[node])*(nn-newsz[node])*2);
	ans+=(sum*sum-res);
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(ll i=1;i<=m;i++){
		ll u,v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	for(ll i=1;i<=n;i++){
		if(vis[i]==0) dfs(i);
	}
	memset(vis,0,sizeof(vis));
	for(ll i=1;i<=n;i++){
		if(vis[i]==0){
			nn=0;
			dfs1(i,i);
			compsz[i]=nn;
			mark[i]=1;
		} 
	}
	memset(vis,0,sizeof(vis));
	for(ll i=1;i<=n;i++){
		if(mark[i]==1){
			nn=compsz[i];
			solve(i);
		}
	}
	cout << ans;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	10572 KB	Output is correct
2	Correct	7 ms	10628 KB	Output is correct
3	Correct	7 ms	10628 KB	Output is correct
4	Correct	7 ms	10572 KB	Output is correct
5	Correct	7 ms	10632 KB	Output is correct
6	Correct	8 ms	10624 KB	Output is correct
7	Incorrect	7 ms	10632 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	140 ms	39488 KB	Output is correct
2	Correct	130 ms	39528 KB	Output is correct
3	Correct	151 ms	39480 KB	Output is correct
4	Correct	145 ms	41540 KB	Output is correct
5	Correct	135 ms	38188 KB	Output is correct
6	Correct	154 ms	39484 KB	Output is correct
7	Correct	177 ms	38596 KB	Output is correct
8	Correct	160 ms	39236 KB	Output is correct
9	Correct	156 ms	37664 KB	Output is correct
10	Correct	174 ms	37780 KB	Output is correct
11	Correct	141 ms	34416 KB	Output is correct
12	Correct	128 ms	34116 KB	Output is correct
13	Correct	134 ms	33808 KB	Output is correct
14	Correct	128 ms	33304 KB	Output is correct
15	Correct	100 ms	31444 KB	Output is correct
16	Correct	100 ms	30548 KB	Output is correct
17	Correct	13 ms	15440 KB	Output is correct
18	Correct	13 ms	15436 KB	Output is correct
19	Correct	13 ms	15444 KB	Output is correct
20	Correct	12 ms	15436 KB	Output is correct
21	Correct	13 ms	15408 KB	Output is correct
22	Correct	12 ms	15364 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	10828 KB	Output is correct
2	Correct	9 ms	10876 KB	Output is correct
3	Correct	9 ms	10828 KB	Output is correct
4	Correct	9 ms	10956 KB	Output is correct
5	Correct	8 ms	10856 KB	Output is correct
6	Correct	8 ms	10828 KB	Output is correct
7	Correct	8 ms	10828 KB	Output is correct
8	Correct	8 ms	10828 KB	Output is correct
9	Correct	8 ms	10900 KB	Output is correct
10	Correct	9 ms	10888 KB	Output is correct
11	Correct	8 ms	10828 KB	Output is correct
12	Correct	9 ms	10828 KB	Output is correct
13	Correct	8 ms	10892 KB	Output is correct
14	Correct	10 ms	10828 KB	Output is correct
15	Correct	8 ms	10828 KB	Output is correct
16	Correct	8 ms	10756 KB	Output is correct
17	Correct	8 ms	10828 KB	Output is correct
18	Correct	8 ms	10844 KB	Output is correct
19	Correct	8 ms	10956 KB	Output is correct
20	Correct	9 ms	10892 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	203 ms	39148 KB	Output is correct
2	Correct	198 ms	39252 KB	Output is correct
3	Correct	230 ms	39136 KB	Output is correct
4	Correct	181 ms	39208 KB	Output is correct
5	Correct	186 ms	39200 KB	Output is correct
6	Correct	178 ms	43060 KB	Output is correct
7	Correct	193 ms	42264 KB	Output is correct
8	Correct	193 ms	41344 KB	Output is correct
9	Correct	201 ms	40552 KB	Output is correct
10	Correct	181 ms	39108 KB	Output is correct
11	Correct	220 ms	40380 KB	Output is correct
12	Correct	177 ms	40448 KB	Output is correct
13	Correct	191 ms	40424 KB	Output is correct
14	Correct	183 ms	40052 KB	Output is correct
15	Correct	157 ms	38412 KB	Output is correct
16	Correct	112 ms	32216 KB	Output is correct
17	Correct	169 ms	42148 KB	Output is correct
18	Correct	169 ms	42156 KB	Output is correct
19	Correct	166 ms	42184 KB	Output is correct
20	Correct	161 ms	41852 KB	Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	200 ms	39292 KB	Output is correct
2	Correct	183 ms	38956 KB	Output is correct
3	Incorrect	188 ms	35476 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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

Submission #403755

Compilation message