oj.uz

Submission #71951

# Submission time Handle Problem Language Result Execution time Memory
71951 2018-08-26T02:53:13 Z KLPP Duathlon (APIO18_duathlon) C++14
23 / 100
 272 ms 53904 KB 
#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;
typedef long long int lld;
lld DP[1000000];
bool visited[1000000];
vector<int>nei[1000000];
lld ans;
bool visited2[1000000];
void DFS(int node,lld dist){//cout<<node+1<<" "<<dist<<endl;
	visited[node]=true;
	lld sum=0;
	//lld square=0;
	//lld totaldist=0;
	for(int i=0;i<nei[node].size();i++){
		int v=nei[node][i];
		if(!visited[v]){
			DFS(v,dist+1);
			sum+=DP[v];
			//square+=DP[v]*DP[v];
		}
	}
	DP[node]=sum+1;
	//ans+=sum*sum-square;
	//cout<<sum*sum-square<<" "<<node+1<<endl;
	//ans+=dist*(dist-1);
}
void DFS2(int node,lld componentsize){
	visited2[node]=true;
	lld sq=componentsize-DP[node];
	sq*=sq;
	for(int i=0;i<nei[node].size();i++){
		int v=nei[node][i];
		if(!visited2[v]){
			DFS2(v,componentsize);
			sq+=DP[v]*DP[v];
		}		
	}
	ans+=(componentsize-1)*(componentsize-1)-sq;
	//cout<<(componentsize-1)*(componentsize-1)-sq<<" "<<node+1<<endl;
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int x,y;
		cin>>x>>y;
		x--;y--;
		nei[x].push_back(y);
		nei[y].push_back(x);
	}
	ans=0;
	for(int i=0;i<n;i++){
		DP[i]=-1;
		visited[i]=false;
		visited2[i]=false;
	}
	for(int i=0;i<n;i++){
		if(!visited[i]){
			DFS(i,0);
			DFS2(i,DP[i]);
		}
	}//for(int i=0;i<n;i++)cout<<DP[i]<<" "<<i+1<<endl;
	cout<<ans<<endl;

	return 0;	
}

Compilation message

count_triplets.cpp: In function 'void DFS(int, lld)':
count_triplets.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<nei[node].size();i++){
              ~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void DFS2(int, lld)':
count_triplets.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<nei[node].size();i++){
              ~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 192 ms 34152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 34152 KB Output is correct
2 Correct 24 ms 34152 KB Output is correct
3 Correct 28 ms 34152 KB Output is correct
4 Correct 23 ms 34152 KB Output is correct
5 Correct 29 ms 34152 KB Output is correct
6 Correct 30 ms 34152 KB Output is correct
7 Correct 26 ms 34152 KB Output is correct
8 Correct 26 ms 34152 KB Output is correct
9 Correct 24 ms 34152 KB Output is correct
10 Correct 23 ms 34152 KB Output is correct
11 Correct 23 ms 34152 KB Output is correct
12 Correct 28 ms 34152 KB Output is correct
13 Correct 29 ms 34152 KB Output is correct
14 Correct 34 ms 34152 KB Output is correct
15 Correct 29 ms 34152 KB Output is correct
16 Correct 24 ms 34152 KB Output is correct
17 Correct 31 ms 34152 KB Output is correct
18 Correct 26 ms 34152 KB Output is correct
19 Correct 24 ms 34152 KB Output is correct
20 Correct 24 ms 34152 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 34152 KB Output is correct
2 Correct 198 ms 34152 KB Output is correct
3 Correct 187 ms 34152 KB Output is correct
4 Correct 180 ms 34152 KB Output is correct
5 Correct 199 ms 34152 KB Output is correct
6 Correct 272 ms 37920 KB Output is correct
7 Correct 248 ms 38060 KB Output is correct
8 Correct 214 ms 38728 KB Output is correct
9 Correct 213 ms 39432 KB Output is correct
10 Correct 180 ms 39692 KB Output is correct
11 Correct 180 ms 40900 KB Output is correct
12 Correct 172 ms 42160 KB Output is correct
13 Correct 193 ms 43608 KB Output is correct
14 Correct 203 ms 44608 KB Output is correct
15 Correct 144 ms 45340 KB Output is correct
16 Correct 93 ms 45340 KB Output is correct
17 Correct 164 ms 47720 KB Output is correct
18 Correct 164 ms 49016 KB Output is correct
19 Correct 136 ms 50236 KB Output is correct
20 Correct 157 ms 51480 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 51480 KB Output is correct
2 Correct 29 ms 51480 KB Output is correct
3 Incorrect 27 ms 51480 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 51480 KB Output is correct
2 Correct 245 ms 52352 KB Output is correct
3 Incorrect 207 ms 53904 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -