Submission #138794

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138794	2019-07-30T10:31:39 Z	FedericoS	Duathlon (APIO18_duathlon)	C++14	31 / 100	1000 ms	1048580 KB

count_triplets

#include <iostream>
#include <vector>
#include <map>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;

bool sub3=true;

ll N,M;
ll x,y;
ll A,B,C,ans;
bool V[300005];
vector<ll> grafo[300005];
ll S[300005];

map <pll,ll> E;

void DFSsub3(int k){

	B++;
	if(V[k])
		return;
	A++;
	C++;
	V[k]=true;

	for(int f:grafo[k])
		DFSsub3(f);}

void DFS(int k, int p=-1){

	for(int f:grafo[k])
		if(f!=p)
			DFS(f,k);

	E[{p,k}]=1;

	for(int f:grafo[k])
		if(f!=p)
			E[{p,k}]+=E[{k,f}];

	E[{k,p}]=C-E[{p,k}];

}

int main(){

	cin>>N>>M;
	for(int i=0;i<M;i++){
		cin>>x>>y;
		grafo[x].push_back(y);
		grafo[y].push_back(x);
	}

	for(int i=1;i<N+1;i++)
		if(grafo[i].size()>2)
			sub3=false;
		
	if(sub3){
		for(int i=1;i<N+1;i++)
			if(!V[i]){
				A=B=0;
				DFSsub3(i);
				if(B-1==2*A)
					ans+=(A*(A-1)*(A-2));
				else	
					ans+=(A*(A-1)*(A-2))/3;
			}
		cout<<ans;}
	else{

		for(int i=1;i<N+1;i++)
			if(!V[i]){
				C=0;
				DFSsub3(i);
				DFS(i);
			}

		for(ll i=1;i<N+1;i++){
			A=B=0;
			for(ll f:grafo[i]){
				A+=E[{i,f}];
				B+=E[{i,f}]*E[{i,f}];
			}
			A=A*A;
			ans+=A-B;
		}

		cout<<ans;

	}

}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	904 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	904 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	192 ms	13860 KB	Output is correct
2	Correct	175 ms	15008 KB	Output is correct
3	Correct	170 ms	13408 KB	Output is correct
4	Correct	174 ms	14276 KB	Output is correct
5	Correct	163 ms	13080 KB	Output is correct
6	Correct	173 ms	12936 KB	Output is correct
7	Correct	163 ms	12408 KB	Output is correct
8	Correct	177 ms	12696 KB	Output is correct
9	Correct	175 ms	12248 KB	Output is correct
10	Correct	171 ms	12384 KB	Output is correct
11	Correct	139 ms	11624 KB	Output is correct
12	Correct	139 ms	11636 KB	Output is correct
13	Correct	151 ms	11448 KB	Output is correct
14	Correct	131 ms	11280 KB	Output is correct
15	Correct	94 ms	10716 KB	Output is correct
16	Correct	94 ms	10736 KB	Output is correct
17	Correct	11 ms	7592 KB	Output is correct
18	Correct	11 ms	7544 KB	Output is correct
19	Correct	11 ms	7544 KB	Output is correct
20	Correct	11 ms	7544 KB	Output is correct
21	Correct	10 ms	7544 KB	Output is correct
22	Correct	10 ms	7544 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	7544 KB	Output is correct
2	Correct	10 ms	7672 KB	Output is correct
3	Correct	10 ms	7544 KB	Output is correct
4	Correct	9 ms	7416 KB	Output is correct
5	Correct	11 ms	7672 KB	Output is correct
6	Correct	11 ms	7544 KB	Output is correct
7	Correct	9 ms	7416 KB	Output is correct
8	Correct	10 ms	7544 KB	Output is correct
9	Correct	10 ms	7544 KB	Output is correct
10	Correct	10 ms	7544 KB	Output is correct
11	Correct	13 ms	7544 KB	Output is correct
12	Correct	13 ms	7544 KB	Output is correct
13	Correct	10 ms	7544 KB	Output is correct
14	Correct	10 ms	7544 KB	Output is correct
15	Correct	10 ms	7544 KB	Output is correct
16	Correct	10 ms	7548 KB	Output is correct
17	Correct	10 ms	7544 KB	Output is correct
18	Correct	10 ms	7544 KB	Output is correct
19	Correct	10 ms	7544 KB	Output is correct
20	Correct	12 ms	7544 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	425 ms	23780 KB	Output is correct
2	Correct	410 ms	23800 KB	Output is correct
3	Correct	401 ms	23692 KB	Output is correct
4	Correct	414 ms	23896 KB	Output is correct
5	Correct	420 ms	23800 KB	Output is correct
6	Correct	171 ms	12408 KB	Output is correct
7	Correct	440 ms	28712 KB	Output is correct
8	Correct	539 ms	27580 KB	Output is correct
9	Correct	535 ms	26196 KB	Output is correct
10	Correct	488 ms	23868 KB	Output is correct
11	Correct	432 ms	23720 KB	Output is correct
12	Correct	429 ms	23720 KB	Output is correct
13	Correct	408 ms	23672 KB	Output is correct
14	Correct	384 ms	23704 KB	Output is correct
15	Correct	387 ms	23368 KB	Output is correct
16	Correct	256 ms	22524 KB	Output is correct
17	Correct	477 ms	24100 KB	Output is correct
18	Correct	529 ms	23992 KB	Output is correct
19	Correct	411 ms	23904 KB	Output is correct
20	Correct	412 ms	23932 KB	Output is correct

Subtask #6
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	7544 KB	Output is correct
2	Correct	10 ms	7544 KB	Output is correct
3	Execution timed out	1133 ms	1021028 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	402 ms	23796 KB	Output is correct
2	Correct	425 ms	23708 KB	Output is correct
3	Execution timed out	1148 ms	709480 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	904 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	904 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Submission #138794

Compilation message