oj.uz

Submission #72125

# Submission time Handle Problem Language Result Execution time Memory
72125 2018-08-26T05:25:13 Z KLPP Duathlon (APIO18_duathlon) C++14
23 / 100
 234 ms 58888 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;
	int edges[n][2];
	for(int i=0;i<m;i++){
		int x,y;
		cin>>x>>y;
		x--;y--;
		edges[i][0]=x;
		edges[i][1]=y;
		nei[x].push_back(y);
		nei[y].push_back(x);
	}
	if(n>50){
	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;
	}
	int component[n][n];
	vector<int>graph[n];
	for(int node=0;node<n;node++){
		for(int j=0;j<m;j++){
			if(edges[j][0]!=node && edges[j][1]!=node){
				graph[edges[j][0]].push_back(edges[j][1]);
				graph[edges[j][1]].push_back(edges[j][0]);
			}
		}
		int color=0;
		for(int i=0;i<n;i++)component[node][i]=-1;
		for(int i=0;i<n;i++){
			if(component[node][i]==-1){
				component[node][i]=color;
				queue<int>q;
				q.push(i);
				while(!q.empty()){
					int u=q.front();q.pop();
					//cout<<u<<" ";
					for(int j=0;j<graph[u].size();j++){
						int v=graph[u][j];
						if(component[node][v]==-1){
							component[node][v]=color;
							q.push(v);
						}
					}
				}
				color++;//cout<<endl;
			}
		}
		/*for(int i=0;i<n;i++)cout<<component[node][i]<<" ";
		cout<<endl;*/
		for(int i=0;i<n;i++)graph[i].clear();
	}
	int cnt=0;
	for(int s=0;s<n;s++){
		for(int f=0;f<n;f++){
			for(int c=0;c<n;c++){
				if(s!=c && s!=f && f!=c){
					bool b=true;
					for(int i=0;i<n;i++){
						if(i!=c){
						if(component[i][c]!=component[i][s] && component[i][c]!=component[i][f]){
							b=false;
						}}
					}cnt+=b;
					/*if(b){
						cout<<s<<" "<<f<<" "<<c<<endl;
					}*/
				}
			}
		}
	}
	cout<<cnt<<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++){
              ~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:94:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j=0;j<graph[u].size();j++){
                  ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23804 KB Output is correct
2 Runtime error 46 ms 47464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23804 KB Output is correct
2 Runtime error 46 ms 47464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 234 ms 58888 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 22 ms 58888 KB Output is correct
2 Correct 24 ms 58888 KB Output is correct
3 Correct 23 ms 58888 KB Output is correct
4 Correct 25 ms 58888 KB Output is correct
5 Correct 23 ms 58888 KB Output is correct
6 Correct 23 ms 58888 KB Output is correct
7 Correct 24 ms 58888 KB Output is correct
8 Correct 24 ms 58888 KB Output is correct
9 Correct 25 ms 58888 KB Output is correct
10 Correct 24 ms 58888 KB Output is correct
11 Correct 25 ms 58888 KB Output is correct
12 Correct 25 ms 58888 KB Output is correct
13 Correct 23 ms 58888 KB Output is correct
14 Correct 23 ms 58888 KB Output is correct
15 Correct 26 ms 58888 KB Output is correct
16 Correct 24 ms 58888 KB Output is correct
17 Correct 25 ms 58888 KB Output is correct
18 Correct 24 ms 58888 KB Output is correct
19 Correct 23 ms 58888 KB Output is correct
20 Correct 24 ms 58888 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 58888 KB Output is correct
2 Correct 172 ms 58888 KB Output is correct
3 Correct 205 ms 58888 KB Output is correct
4 Correct 227 ms 58888 KB Output is correct
5 Correct 185 ms 58888 KB Output is correct
6 Correct 231 ms 58888 KB Output is correct
7 Correct 200 ms 58888 KB Output is correct
8 Correct 199 ms 58888 KB Output is correct
9 Correct 231 ms 58888 KB Output is correct
10 Correct 201 ms 58888 KB Output is correct
11 Correct 156 ms 58888 KB Output is correct
12 Correct 213 ms 58888 KB Output is correct
13 Correct 228 ms 58888 KB Output is correct
14 Correct 152 ms 58888 KB Output is correct
15 Correct 151 ms 58888 KB Output is correct
16 Correct 103 ms 58888 KB Output is correct
17 Correct 134 ms 58888 KB Output is correct
18 Correct 139 ms 58888 KB Output is correct
19 Correct 151 ms 58888 KB Output is correct
20 Correct 147 ms 58888 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 58888 KB Output is correct
2 Correct 182 ms 58888 KB Output is correct
3 Incorrect 168 ms 58888 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23804 KB Output is correct
2 Runtime error 46 ms 47464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23804 KB Output is correct
2 Runtime error 46 ms 47464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -