oj.uz

Submission #138793

# Submission time Handle Problem Language Result Execution time Memory
138793 2019-07-30T10:31:12 Z FedericoS Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048580 KB 
#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;

	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 855 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 855 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

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 7544 KB Output is correct
3 Correct 10 ms 7548 KB Output is correct
4 Correct 10 ms 7672 KB Output is correct
5 Correct 11 ms 7544 KB Output is correct
6 Correct 10 ms 7672 KB Output is correct
7 Correct 10 ms 7544 KB Output is correct
8 Correct 10 ms 7672 KB Output is correct
9 Correct 13 ms 7704 KB Output is correct
10 Correct 10 ms 7544 KB Output is correct
11 Correct 10 ms 7544 KB Output is correct
12 Correct 19 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 12 ms 7544 KB Output is correct
17 Correct 10 ms 7544 KB Output is correct
18 Correct 10 ms 7544 KB Output is correct
19 Correct 12 ms 7544 KB Output is correct
20 Correct 10 ms 7544 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 23984 KB Output is correct
2 Correct 463 ms 23932 KB Output is correct
3 Correct 394 ms 24096 KB Output is correct
4 Correct 399 ms 23892 KB Output is correct
5 Correct 397 ms 24056 KB Output is correct
6 Correct 434 ms 30912 KB Output is correct
7 Correct 441 ms 29048 KB Output is correct
8 Correct 470 ms 27656 KB Output is correct
9 Correct 469 ms 26384 KB Output is correct
10 Correct 410 ms 24056 KB Output is correct
11 Correct 409 ms 25116 KB Output is correct
12 Correct 420 ms 25032 KB Output is correct
13 Correct 493 ms 25208 KB Output is correct
14 Correct 392 ms 24628 KB Output is correct
15 Correct 437 ms 24448 KB Output is correct
16 Correct 256 ms 22976 KB Output is correct
17 Correct 448 ms 25172 KB Output is correct
18 Correct 465 ms 25312 KB Output is correct
19 Correct 432 ms 25160 KB Output is correct
20 Correct 405 ms 25276 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 23952 KB Output is correct
2 Correct 413 ms 23780 KB Output is correct
3 Execution timed out 1143 ms 742968 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 855 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 855 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -