oj.uz

Submission #91106

# Submission time Handle Problem Language Result Execution time Memory
91106 2018-12-26T09:28:23 Z Just_Solve_The_Problem Shymbulak (IZhO14_shymbulak) C++11
0 / 100
 1500 ms 10428 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6648 KB Output is correct
2 Correct 7 ms 6652 KB Output is correct
3 Correct 7 ms 6688 KB Output is correct
4 Correct 7 ms 6688 KB Output is correct
5 Correct 7 ms 6688 KB Output is correct
6 Incorrect 8 ms 6688 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 6764 KB Output is correct
2 Correct 40 ms 6804 KB Output is correct
3 Incorrect 55 ms 6804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1571 ms 10428 KB Time limit exceeded
2 Halted 0 ms 0 KB -