Submission #171787

#	Time	Username	Problem	Language	Result	Execution time	Memory
171787		Lightning	Shymbulak (IZhO14_shymbulak)	C++14	50 / 100	1542 ms	10012 KiB

shymbulak

#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 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 50