Submission #392643

#	Time	Username	Problem	Language	Result	Execution time	Memory
392643		vanic	Shymbulak (IZhO14_shymbulak)	C++14	30 / 100	201 ms	1348 KiB

shymbulak

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <bitset>
#include <vector>

using namespace std;

const int maxn=505;
const int inf=1e9;

int n;
int ms[maxn][maxn];
vector < int > s[maxn];
bitset < maxn > bio;
int maksi;

int nadji(int x, int y, int dep){
	if(x==y){
		if(dep==maksi){
			return 1;
		}
		return 0;
	}
	bio[x]=1;
	int br=0;
	for(int i=0; i<(int)s[x].size(); i++){
		if(!bio[s[x][i]]){
			br+=nadji(s[x][i], y, dep+1);
		}
	}
	bio[x]=0;
	return br;
}

int main(){
	scanf("%d", &n);
	assert(n<maxn);
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			ms[i][j]=inf;
		}
		ms[i][i]=0;
	}
	int a, b;
	for(int i=0; i<n; i++){
		scanf("%d%d", &a, &b);
		a--;
		b--;
		s[a].push_back(b);
		s[b].push_back(a);
		ms[a][b]=1;
		ms[b][a]=1;
	}
	for(int k=0; k<n; k++){
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(ms[i][k]+ms[k][j]<ms[i][j]){
					ms[i][j]=ms[i][k]+ms[k][j];
				}
			}
		}
	}
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			maksi=max(maksi,  ms[i][j]);
		}
	}
	int sol=0;
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			if(ms[i][j]==maksi){
				sol+=nadji(i, j, 0);
				bio.reset();
			}
		}
	}
	printf("%d\n", sol);
	return 0;
}

Compilation message (stderr)

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
shymbulak.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50