oj.uz

Submission #72200

# Submission time Handle Problem Language Result Execution time Memory
72200 2018-08-26T05:55:09 Z KLPP Duathlon (APIO18_duathlon) C++14
23 / 100
 252 ms 34044 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[m][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);
	}
	//for(int i=0;i<m;i++)cout<<edges[i][0]<<" "<<edges[i][1]<<endl;
	bool enter=true;
	for(int i=0;i<n;i++){
		if(nei[i].size()>2)enter=false;
	}
	if(enter){
	int component[n];
	
	for(int i=0;i<n;i++){
		component[i]=-1;
		
	}
	lld ans=0;
	int color=0;
	for(int i=0;i<n;i++){
		if(component[i]==-1){
			component[i]=color;
			
			queue<int>q;
			q.push(i);
			bool cycle=false;
			lld size=0;
			while(!q.empty()){size++;
				int u=q.front();q.pop();
				//cout<<u<<" ";
				for(int j=0;j<nei[u].size();j++){
					int v=nei[u][j];
					if(component[v]==-1){
						component[v]=color;
						q.push(v);
						
					}
				}
			}
			color++;//cout<<endl;
			int edges=0;
			for(int i=0;i<n;i++)edges+=nei[i].size();
			if(edges==2*n)cycle=true;
			//cout<<cycle<<endl;
			
			if(cycle){
				ans+=size*(size-1)*(size-2);
			}else{
				ans+=size*(size-1)*(size-2)/3;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
	}
	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;
	}
	if(n<=50){
	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){//cout<<edges[j][0]<<" "<<edges[j][1]<<" "<<j<<endl;
				graph[edges[j][0]].push_back(edges[j][1]);
				graph[edges[j][1]].push_back(edges[j][0]);
				//cout<<edges[j][0]<<" "<<edges[j][1]<<" "<<j<<endl;
			}
		}
		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++)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;
				}
			}
		}
	}
	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:85:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<nei[u].size();j++){
                 ~^~~~~~~~~~~~~~
count_triplets.cpp:147: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 24 ms 23800 KB Output is correct
2 Correct 27 ms 23800 KB Output is correct
3 Correct 24 ms 23944 KB Output is correct
4 Correct 23 ms 23944 KB Output is correct
5 Correct 22 ms 23944 KB Output is correct
6 Correct 24 ms 24020 KB Output is correct
7 Correct 23 ms 24020 KB Output is correct
8 Correct 23 ms 24020 KB Output is correct
9 Correct 23 ms 24020 KB Output is correct
10 Correct 25 ms 24148 KB Output is correct
11 Correct 24 ms 24148 KB Output is correct
12 Correct 26 ms 24148 KB Output is correct
13 Correct 27 ms 24148 KB Output is correct
14 Correct 24 ms 24148 KB Output is correct
15 Correct 24 ms 24148 KB Output is correct
16 Correct 23 ms 24148 KB Output is correct
17 Correct 22 ms 24148 KB Output is correct
18 Correct 24 ms 24148 KB Output is correct
19 Correct 25 ms 24148 KB Output is correct
20 Incorrect 30 ms 24148 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 27 ms 23800 KB Output is correct
3 Correct 24 ms 23944 KB Output is correct
4 Correct 23 ms 23944 KB Output is correct
5 Correct 22 ms 23944 KB Output is correct
6 Correct 24 ms 24020 KB Output is correct
7 Correct 23 ms 24020 KB Output is correct
8 Correct 23 ms 24020 KB Output is correct
9 Correct 23 ms 24020 KB Output is correct
10 Correct 25 ms 24148 KB Output is correct
11 Correct 24 ms 24148 KB Output is correct
12 Correct 26 ms 24148 KB Output is correct
13 Correct 27 ms 24148 KB Output is correct
14 Correct 24 ms 24148 KB Output is correct
15 Correct 24 ms 24148 KB Output is correct
16 Correct 23 ms 24148 KB Output is correct
17 Correct 22 ms 24148 KB Output is correct
18 Correct 24 ms 24148 KB Output is correct
19 Correct 25 ms 24148 KB Output is correct
20 Incorrect 30 ms 24148 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 31772 KB Output is correct
2 Correct 210 ms 31772 KB Output is correct
3 Correct 177 ms 31772 KB Output is correct
4 Correct 190 ms 31772 KB Output is correct
5 Correct 200 ms 31808 KB Output is correct
6 Correct 197 ms 31808 KB Output is correct
7 Correct 252 ms 34044 KB Output is correct
8 Correct 207 ms 34044 KB Output is correct
9 Correct 240 ms 34044 KB Output is correct
10 Correct 180 ms 34044 KB Output is correct
11 Correct 169 ms 34044 KB Output is correct
12 Correct 219 ms 34044 KB Output is correct
13 Correct 208 ms 34044 KB Output is correct
14 Correct 169 ms 34044 KB Output is correct
15 Correct 145 ms 34044 KB Output is correct
16 Correct 96 ms 34044 KB Output is correct
17 Correct 138 ms 34044 KB Output is correct
18 Correct 155 ms 34044 KB Output is correct
19 Correct 139 ms 34044 KB Output is correct
20 Correct 136 ms 34044 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 34044 KB Output is correct
2 Correct 231 ms 34044 KB Output is correct
3 Incorrect 226 ms 34044 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 27 ms 23800 KB Output is correct
3 Correct 24 ms 23944 KB Output is correct
4 Correct 23 ms 23944 KB Output is correct
5 Correct 22 ms 23944 KB Output is correct
6 Correct 24 ms 24020 KB Output is correct
7 Correct 23 ms 24020 KB Output is correct
8 Correct 23 ms 24020 KB Output is correct
9 Correct 23 ms 24020 KB Output is correct
10 Correct 25 ms 24148 KB Output is correct
11 Correct 24 ms 24148 KB Output is correct
12 Correct 26 ms 24148 KB Output is correct
13 Correct 27 ms 24148 KB Output is correct
14 Correct 24 ms 24148 KB Output is correct
15 Correct 24 ms 24148 KB Output is correct
16 Correct 23 ms 24148 KB Output is correct
17 Correct 22 ms 24148 KB Output is correct
18 Correct 24 ms 24148 KB Output is correct
19 Correct 25 ms 24148 KB Output is correct
20 Incorrect 30 ms 24148 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 27 ms 23800 KB Output is correct
3 Correct 24 ms 23944 KB Output is correct
4 Correct 23 ms 23944 KB Output is correct
5 Correct 22 ms 23944 KB Output is correct
6 Correct 24 ms 24020 KB Output is correct
7 Correct 23 ms 24020 KB Output is correct
8 Correct 23 ms 24020 KB Output is correct
9 Correct 23 ms 24020 KB Output is correct
10 Correct 25 ms 24148 KB Output is correct
11 Correct 24 ms 24148 KB Output is correct
12 Correct 26 ms 24148 KB Output is correct
13 Correct 27 ms 24148 KB Output is correct
14 Correct 24 ms 24148 KB Output is correct
15 Correct 24 ms 24148 KB Output is correct
16 Correct 23 ms 24148 KB Output is correct
17 Correct 22 ms 24148 KB Output is correct
18 Correct 24 ms 24148 KB Output is correct
19 Correct 25 ms 24148 KB Output is correct
20 Incorrect 30 ms 24148 KB Output isn't correct
21 Halted 0 ms 0 KB -