답안 #72118 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72118	2018-08-26T05:22:36 Z	KLPP	철인 이종 경기 (APIO18_duathlon)	C++14	23 / 100	235 ms	58792 KB

count_triplets

#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];
	for(int node=0;node<n;node++){
		vector<int>graph[n];
		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;*/
	}
	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

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	23800 KB	Output is correct
2	Runtime error	46 ms	47588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	23800 KB	Output is correct
2	Runtime error	46 ms	47588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	208 ms	58792 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	58792 KB	Output is correct
2	Correct	25 ms	58792 KB	Output is correct
3	Correct	24 ms	58792 KB	Output is correct
4	Correct	26 ms	58792 KB	Output is correct
5	Correct	25 ms	58792 KB	Output is correct
6	Correct	27 ms	58792 KB	Output is correct
7	Correct	23 ms	58792 KB	Output is correct
8	Correct	23 ms	58792 KB	Output is correct
9	Correct	25 ms	58792 KB	Output is correct
10	Correct	27 ms	58792 KB	Output is correct
11	Correct	25 ms	58792 KB	Output is correct
12	Correct	26 ms	58792 KB	Output is correct
13	Correct	26 ms	58792 KB	Output is correct
14	Correct	24 ms	58792 KB	Output is correct
15	Correct	22 ms	58792 KB	Output is correct
16	Correct	22 ms	58792 KB	Output is correct
17	Correct	23 ms	58792 KB	Output is correct
18	Correct	22 ms	58792 KB	Output is correct
19	Correct	23 ms	58792 KB	Output is correct
20	Correct	23 ms	58792 KB	Output is correct

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	161 ms	58792 KB	Output is correct
2	Correct	208 ms	58792 KB	Output is correct
3	Correct	182 ms	58792 KB	Output is correct
4	Correct	185 ms	58792 KB	Output is correct
5	Correct	200 ms	58792 KB	Output is correct
6	Correct	214 ms	58792 KB	Output is correct
7	Correct	235 ms	58792 KB	Output is correct
8	Correct	209 ms	58792 KB	Output is correct
9	Correct	185 ms	58792 KB	Output is correct
10	Correct	171 ms	58792 KB	Output is correct
11	Correct	203 ms	58792 KB	Output is correct
12	Correct	188 ms	58792 KB	Output is correct
13	Correct	234 ms	58792 KB	Output is correct
14	Correct	182 ms	58792 KB	Output is correct
15	Correct	184 ms	58792 KB	Output is correct
16	Correct	125 ms	58792 KB	Output is correct
17	Correct	141 ms	58792 KB	Output is correct
18	Correct	176 ms	58792 KB	Output is correct
19	Correct	172 ms	58792 KB	Output is correct
20	Correct	150 ms	58792 KB	Output is correct

Subtask #6
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	58792 KB	Output is correct
2	Correct	24 ms	58792 KB	Output is correct
3	Incorrect	23 ms	58792 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	202 ms	58792 KB	Output is correct
2	Correct	217 ms	58792 KB	Output is correct
3	Incorrect	209 ms	58792 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	23800 KB	Output is correct
2	Runtime error	46 ms	47588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	23800 KB	Output is correct
2	Runtime error	46 ms	47588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Halted	0 ms	0 KB	-