Submission #650779

#	Time	Username	Problem	Language	Result	Execution time	Memory
650779		MilosMilutinovic	Duathlon (APIO18_duathlon)	C++14	0 / 100	162 ms	26260 KiB

count_triplets

//todo
#include <bits/stdc++.h>
using namespace std;
const int N=100050;
int n,m,dep[N],mn[N];
vector<int> E[N];
bool was[N],art[N];
void DFS_ART(int v){
	was[v]=true;
	mn[v]=1e9;
	int my=1e9;
	bool leaf=true;
	for(int u:E[v]){
		if(!was[u]){
			dep[u]=dep[v]+1;
			DFS_ART(u);
			mn[v]=min(mn[v],mn[u]);
			leaf=false;
		}else my=min(my,dep[u]);
	}
	if(mn[v]<dep[v]||leaf||E[v].size()==1)art[v]=false;
	else art[v]=true;
	mn[v]=min(mn[v],my);
}
int tsz,block_sz[2*N];
vector<int> G[N];
void AddEdge(int u,int v){
	printf("AddEdge u=%i v=%i\n",u,v);
	block_sz[v]++;
	G[u].push_back(v);
	G[v].push_back(u);
}
void DFS_G(int v,bool pp){
	was[v]=true;
	AddEdge(v,tsz);
	for(int u:E[v]){
		if(was[u])continue;
		//if(art[v]&&art[u])AddEdge(u,v);
		if(art[v]&&!art[u]){
			++tsz;
			AddEdge(v,tsz);
		}
		DFS_G(u,false);
	}
}
long long C2(long long n){return n*(n-1)/2;}
long long C3(long long n){return n*(n-1)*(n-2);}
long long ans=0;
int sz[2*N];
void DFS(int v,int par){
	printf("%i %i\n",v,par);
	if(v<=n)sz[v]++;
	for(int u:G[v]){
		sz[v]+=sz[u];
		if(v>n)assert(u<=n);
		if(v>n)ans+=(block_sz[v]-1)*2*C2(sz[u]-1);
		if(u==par)continue;
		DFS(u,v);
	}
}
int main(){
	scanf("%i%i",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;scanf("%i%i",&u,&v);
		E[u].push_back(v);
		E[v].push_back(u);
	}
	DFS_ART(1);
	int root=-1;
	for(int i=1;i<=n;i++)if(art[i])root=i;
	if(root==-1){
		printf("%lld",C3(n));
		return 0;
	}
	for(int i=1;i<=n;i++)was[i]=false;
	tsz=n+1;
	for(int i=1;i<=n;i++)printf("%i ",art[i]);
	DFS_G(root,true);
	for(int i=n+1;i<=tsz;i++)printf("%i ",block_sz[i]); puts("");
	DFS(n+1,0);
	for(int i=1;i<=tsz;i++)printf("%i ",sz[i]);
	printf("%lld\n",C3(n));
	printf("%lld\n",C3(n)-ans);
	return 0;
}
/*
4 3
1 2
2 3
3 4

4 4
1 2
2 3
3 4
4 2
*/

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:79:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   79 |  for(int i=n+1;i<=tsz;i++)printf("%i ",block_sz[i]); puts("");
      |  ^~~
count_triplets.cpp:79:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   79 |  for(int i=n+1;i<=tsz;i++)printf("%i ",block_sz[i]); puts("");
      |                                                      ^~~~
count_triplets.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%i%i",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
count_triplets.cpp:64:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   int u,v;scanf("%i%i",&u,&v);
      |           ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10