oj.uz

Submission #316649

# Submission time Handle Problem Language Result Execution time Memory
316649 2020-10-27T01:36:17 Z shrek12357 Shymbulak (IZhO14_shymbulak) C++14
30 / 100
 1500 ms 59348 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
#define ll long long
//cin.tie(0);ios_base::sync_with_stdio(0); 

const int MAXN = 2*1e6+5;
int n;
vector<int> adjList[MAXN];

int cur = 0, cnt = 0;

void bfs(int src) {
	int dist[MAXN];
	for (int i = 0; i < MAXN; i++) {
		dist[i] = INT_MAX;
	}
	queue<int> q;
	q.push(src);
	dist[src] = 0;
	while (q.size() > 0) {
		int cn = q.front();
		q.pop();
		for (auto i : adjList[cn]) {
			if (dist[i] >= dist[cn] + 1) {
				q.push(i);
				dist[i] = dist[cn] + 1;
				if (cur == dist[i]) {
					cnt++;
				}
				else if (cur < dist[i]) {
					cur = dist[i];
					cnt = 1;
				}
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		adjList[a].push_back(b);
		adjList[b].push_back(a);
	}
	int ans = 0, best = 0;
	for (int i = 0; i < n; i++) {
		cur = 0;
		cnt = 0;
		bfs(i);
		if (cur == ans) {
			best += cnt;
		}
		else if (cur > ans) {
			ans = cur;
			best = cnt;
		}
	}
	cout << best/2 << endl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 55040 KB Output is correct
2 Correct 43 ms 55040 KB Output is correct
3 Correct 44 ms 55032 KB Output is correct
4 Correct 45 ms 55032 KB Output is correct
5 Correct 59 ms 55040 KB Output is correct
6 Correct 65 ms 55160 KB Output is correct
7 Correct 54 ms 55040 KB Output is correct
8 Correct 64 ms 55032 KB Output is correct
9 Correct 65 ms 55040 KB Output is correct
10 Correct 60 ms 55040 KB Output is correct
11 Correct 63 ms 55040 KB Output is correct
12 Correct 56 ms 55032 KB Output is correct
13 Correct 226 ms 55036 KB Output is correct
14 Correct 626 ms 55160 KB Output is correct
15 Correct 637 ms 55160 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 904 ms 55160 KB Output is correct
2 Correct 1002 ms 55160 KB Output is correct
3 Correct 1244 ms 55168 KB Output is correct
4 Correct 1264 ms 55160 KB Output is correct
5 Execution timed out 1604 ms 55288 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

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