Submission #91106

#	Time	Username	Problem	Language	Result	Execution time	Memory
91106		Just_Solve_The_Problem	Shymbulak (IZhO14_shymbulak)	C++11	0 / 100	1571 ms	10428 KiB

shymbulak

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = (int)2e5 + 7;

vector < int > gr[N];
int n;
int used[N], deg[N];
ll ans = 0;
int diam;
int dist[N];

void bfs(int v) {
	memset(used, 0, sizeof used);
	queue < int > q;
	q.push(v);
	used[v] = 1;
	while (!q.empty()) {
		v = q.front();
		q.pop();
		for (int to : gr[v]) {
			if (used[to] == 0) {
				used[to] = used[v] + 1;
				q.push(to);
			}
		}
	}
}

void bfs1(int v) {
	memset(dist, 0, sizeof dist);
	queue < int > q;
	q.push(v);
	dist[v] = 1;
	int asd = v;
	int res = 0;
	int mx = 0;
	while (!q.empty()) {
		v = q.front();
		q.pop();
		for (int to : gr[v]) {
			if (dist[to] == 0) {
				dist[to] = dist[v] + 1;
				mx = max(mx, dist[to]);
				q.push(to);
			} else if (dist[v] + 1 == dist[to]) {
				res = 1;
			}
		}
	}
	if (mx - 1 == diam) {
		int val = 0;
		for (int i = 1; i <= n; i++) {
			if (mx == dist[i]) val++;
		}
		ans += val;
		if (res) {
			ans += val;
		}
	}
}

main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		gr[u].push_back(v);
		gr[v].push_back(u);
		deg[u]++;
		deg[v]++;
	}
	int mx = 0;
	bfs(1);
	for (int i = 1; i <= n; i++) {
		if (used[i] > used[mx]) mx = i;
	} 
	bfs(mx);
	mx = 0;
	for (int i = 1; i <= n; i++) {
		if (used[i] > used[mx]) {
			mx = i;
		}
	}
	diam = used[mx] - 1;
	for (int i = 1; i <= n; i++) {
		bfs1(i);
	}
	cout << ans / 2;
}

Compilation message (stderr)

shymbulak.cpp: In function 'void bfs1(int)':
shymbulak.cpp:38:6: warning: unused variable 'asd' [-Wunused-variable]
  int asd = v;
      ^~~
shymbulak.cpp: At global scope:
shymbulak.cpp:66:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
shymbulak.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

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