oj.uz

답안 #88362

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
88362 2018-12-05T13:25:05 Z dimash241 관광지 (IZhO14_shymbulak) C++17
50 / 100
 1500 ms 20472 KB 
# include <stdio.h>
# include <bits/stdc++.h>


#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define For(i,x,y)  for (int i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (int i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

using namespace std;

inline bool isvowel (char c) {
	c = tolower(c);
    if (c == 'a' || c == 'e' || c == 'i' || c == 'y' || c == 'o' || c == 'u') return 1;
    return 0;
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k;
queue < int > q;  
vector < int > g[N];
pair < int, int > get (int v) {
	vector < int > d(n + 1, -1);
	vector < int > cnt(n + 1, 0);
	d[v] = 0;
	cnt[v] = 1;
	q.push(v);
	while (q.size()) {
		int v = q.front();
		q.pop();

		for (auto 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 mx = -1, ans = 0;
	For (i, 1, n) {
		if (d[i] > mx) {
			mx = d[i];
			ans = cnt[i];
		} else if (d[i] == mx) {
			ans += cnt[i];
		}
	}

	return mp(mx, ans);
}

int main () {               
    cin >> n;
    For (i, 1, n) {
    	int l, r;
    	cin >> l >> r;
    	g[l].pb(r);
    	g[r].pb(l);
    }

    int mx = -1, ans = 0;
    For (i, 1, n) {
    	pair < int, int > cur = get(i);

    	//cout << i << ' ' << cur.F << ' ' << cur.S << '\n';
    	if (cur.F > mx) mx = cur.F, ans = cur.S;
    	else if (cur.F == mx) ans += cur.S;
    }

    cout << ans / 2;
    return Accepted;
}

// Coded By OB

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 14328 KB Output is correct
2 Correct 13 ms 14456 KB Output is correct
3 Correct 13 ms 14696 KB Output is correct
4 Correct 13 ms 14696 KB Output is correct
5 Correct 13 ms 14696 KB Output is correct
6 Correct 14 ms 14696 KB Output is correct
7 Correct 14 ms 14696 KB Output is correct
8 Correct 14 ms 14696 KB Output is correct
9 Correct 13 ms 14776 KB Output is correct
10 Correct 14 ms 14776 KB Output is correct
11 Correct 13 ms 14776 KB Output is correct
12 Correct 13 ms 14820 KB Output is correct
13 Correct 14 ms 14820 KB Output is correct
14 Correct 18 ms 14820 KB Output is correct
15 Correct 19 ms 14820 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 14880 KB Output is correct
2 Correct 22 ms 14880 KB Output is correct
3 Correct 36 ms 14880 KB Output is correct
4 Correct 31 ms 15016 KB Output is correct
5 Correct 573 ms 15212 KB Output is correct
6 Correct 400 ms 15404 KB Output is correct
7 Correct 684 ms 15404 KB Output is correct
8 Correct 760 ms 15516 KB Output is correct
9 Correct 718 ms 15516 KB Output is correct
10 Correct 621 ms 15528 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1577 ms 20472 KB Time limit exceeded
2 Halted 0 ms 0 KB -