oj.uz

Submission #408061

# Submission time Handle Problem Language Result Execution time Memory
408061 2021-05-19T05:49:26 Z juggernaut Duathlon (APIO18_duathlon) C++17
23 / 100
 1000 ms 1048580 KB 
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
int n,m;
int sz[100005];
vector<int>g[100005];
void dfs(int v,int p){
	sz[v]=1;
	for(int to:g[v])if(to!=p){
		dfs(to,v);
		sz[v]+=sz[to];
	}
}
int root;
ll ans=0;
void calc(int v,int p){
	ll sum=0;
	vector<int>vec;
	for(int to:g[v])if(to!=p)vec.push_back(sz[to]);
	if(root^v)vec.push_back(sz[root]-sz[v]);
	for(int x:vec)sum+=x;
	for(int x:vec){
		sum-=x;
		ans+=1ll*x*sum;
		sum+=x;
	}
	for(int to:g[v])if(to!=p)calc(to,v);
}
int main(){
	scanf("%d%d",&n,&m);
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(root=1;root<=n;root++)if(!sz[root])dfs(root,root),calc(root,root);
	printf("%lld",ans);
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
count_triplets.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 514 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 514 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 3 ms 2656 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 4 ms 2764 KB Output is correct
6 Correct 4 ms 2648 KB Output is correct
7 Correct 4 ms 2724 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 3 ms 2636 KB Output is correct
10 Correct 4 ms 2636 KB Output is correct
11 Correct 3 ms 2688 KB Output is correct
12 Correct 3 ms 2652 KB Output is correct
13 Correct 3 ms 2636 KB Output is correct
14 Correct 3 ms 2636 KB Output is correct
15 Correct 3 ms 2636 KB Output is correct
16 Correct 3 ms 2636 KB Output is correct
17 Correct 3 ms 2636 KB Output is correct
18 Correct 3 ms 2636 KB Output is correct
19 Correct 3 ms 2636 KB Output is correct
20 Correct 3 ms 2656 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 6252 KB Output is correct
2 Correct 95 ms 6772 KB Output is correct
3 Correct 102 ms 6748 KB Output is correct
4 Correct 106 ms 6732 KB Output is correct
5 Correct 69 ms 6724 KB Output is correct
6 Correct 106 ms 15164 KB Output is correct
7 Correct 102 ms 12252 KB Output is correct
8 Correct 137 ms 10856 KB Output is correct
9 Correct 145 ms 9384 KB Output is correct
10 Correct 137 ms 6756 KB Output is correct
11 Correct 113 ms 6768 KB Output is correct
12 Correct 89 ms 6764 KB Output is correct
13 Correct 112 ms 6788 KB Output is correct
14 Correct 74 ms 6588 KB Output is correct
15 Correct 79 ms 6456 KB Output is correct
16 Correct 42 ms 5872 KB Output is correct
17 Correct 77 ms 7728 KB Output is correct
18 Correct 64 ms 7544 KB Output is correct
19 Correct 53 ms 7632 KB Output is correct
20 Correct 65 ms 7532 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Runtime error 688 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 6252 KB Output is correct
2 Correct 94 ms 6592 KB Output is correct
3 Runtime error 790 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 514 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 514 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -