oj.uz

Submission #171787

# Submission time Handle Problem Language Result Execution time Memory
171787 2019-12-30T12:02:59 Z Lightning Shymbulak (IZhO14_shymbulak) C++14
50 / 100
 1500 ms 10012 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define show(a) cerr << #a <<" -> "<< a <<"\n"
#define fo(a, b, c, d) for(int (a) = (b); (a) <= (c); (a) += (d))
#define foo(a, b, c ,d) for(int (a) = (b); (a) >= (c); (a) -= (d))
//#define int ll

const int N = 2e5 + 5;
const int INF = 1e9 + 5;

int n, d[N], cnt[N], mx, ans;
vector <int> g[N];
queue <int> q;

void bfs(int st) {
	for(int i = 1; i <= n; ++i) {
		d[i] = -1;
		cnt[i] = 0;
	}
	d[st] = 0;
	cnt[st] = 1;
	q.push(st);
	while(sz(q)) {
		int v = q.front();
		q.pop();
		for(int to : g[v]) {
			if(d[to] == -1) {
				d[to] = d[v] + 1;
				cnt[to] = cnt[v];
				q.push(to);
			} else if(d[to] == d[v] + 1) {
				cnt[to] += cnt[v];
			}
		}
	}
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		int a, b;
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a); 
	}
	for(int i = 1; i <= n; ++i) {
		bfs(i);
		int curmx = 0, res = 0;
		for(int j = 1; j <= n; ++j) {
			if(curmx < d[j]) {
				curmx = d[j];
				res = cnt[j];
			} else if(curmx == d[j]) {
				res += cnt[j];
			}
		}
		if(mx < curmx) {
			mx = curmx;
			ans = res;
		} else if(mx == curmx) {
			ans += res;
		}
	}
	cout << ans / 2;
	return 0;
}
/*
	If you only do what you can do, 
	You will never be more than you are now!
---------------------- -------------------------------------------- ---------------------- ----------------------
	We must all suffer from one of two pains: the pain of discipline or the pain of regret. 
	The difference is discipline weighs grams while regret weighs tons.
*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5116 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 6 ms 5112 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct
13 Correct 6 ms 5112 KB Output is correct
14 Correct 11 ms 4984 KB Output is correct
15 Correct 11 ms 4984 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5112 KB Output is correct
2 Correct 14 ms 5112 KB Output is correct
3 Correct 26 ms 5112 KB Output is correct
4 Correct 26 ms 5112 KB Output is correct
5 Correct 631 ms 5244 KB Output is correct
6 Correct 388 ms 5368 KB Output is correct
7 Correct 815 ms 5240 KB Output is correct
8 Correct 751 ms 5368 KB Output is correct
9 Correct 613 ms 5368 KB Output is correct
10 Correct 672 ms 5340 KB Output is correct

Subtask #3
0 / 50.0

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