oj.uz

답안 #17958

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
17958 2016-01-13T09:46:24 Z Adilkhan 관광지 (IZhO14_shymbulak) C++
26 / 100
 1500 ms 35144 KB 
#include <bits/stdc++.h>

#define pb push_back
#define endl "\n"
#define mp make_pair 
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define fname ""
#define sz(x) (int)(x.size())

typedef long long ll;

using namespace std;

const ll N = (ll)(5e5) + 322;
const ll INF = (ll)(1e9);
const ll mod = (ll)(1e9) + 7;
const double eps = 1e-9;

ll d[N][3], n, m, mx, sum;
        
vector <ll> v[N];

queue <ll> q;

void fmbfs(ll s) {
	memset(d, -1, sizeof d);
	for (int i = 1; i <= n; ++i) d[i][1] = 0;
	q.push(s);
	d[s][0] = 0; d[s][1] = 1;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int j = 0; j < sz(v[x]); ++j) {
			int to = v[x][j];
			if (d[to][0] == -1) {
				d[to][0] = d[x][0] + 1;
				d[to][1] += d[x][1];
				q.push(to);			
				continue;
			}		
			if (d[to][0] == d[x][0] + 1) {
				d[to][1] += d[x][1];
			}
		}	
	}	
	for (int i = 1; i <= n; ++i) {
		mx = max(mx, d[i][0]);
	}         
}

bool bfs(ll s) {
	ll z = sum;
	memset(d, -1, sizeof d);
	for (int i = 1; i <= n; ++i) d[i][1] = 0;
	q.push(s);
	d[s][0] = 0; d[s][1] = 1;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int j = 0; j < sz(v[x]); ++j) {
		  int to = v[x][j];
			if (d[to][0] == -1) {
				d[to][0] = d[x][0] + 1;
				d[to][1] += d[x][1];
				q.push(to);			
				continue;
			}		
			if (d[to][0] == d[x][0] + 1) {
				d[to][1] += d[x][1];
			}
		}	
	}	
	for (int i = 1; i <= n; ++i) {
		if (mx == d[i][0]) {
			sum += d[i][1];
		}
	}
	return (z == sum);
}

int main () {
//	freopen(fname".in", "r", stdin);
	//freopen(fname".out", "w", stdout);
	scanf("%lld", &n);
	for (int i = 1; i <= n; ++i) {
		ll x, y; scanf("%lld%lld", &x, &y);
		v[x].pb(y); v[y].pb(x);
	}
	for (int i = 1; i <= n; ++i) {
		fmbfs(i);
	}
	for (int i = 1; i <= n; ++i) {
		if (!bfs(i)) {
			v[i].clear();			
		}      
	}
	printf("%lld", sum / 2);
	return 0;
}

Subtask #1
24.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 25176 KB Output isn't correct
2 Correct 15 ms 25176 KB Output is correct
3 Correct 11 ms 25176 KB Output is correct
4 Correct 19 ms 25176 KB Output is correct
5 Incorrect 30 ms 25176 KB Output isn't correct
6 Correct 42 ms 25176 KB Output is correct
7 Correct 25 ms 25176 KB Output is correct
8 Correct 36 ms 25176 KB Output is correct
9 Correct 40 ms 25176 KB Output is correct
10 Correct 35 ms 25176 KB Output is correct
11 Correct 39 ms 25176 KB Output is correct
12 Incorrect 32 ms 25176 KB Output isn't correct
13 Correct 265 ms 25176 KB Output is correct
14 Correct 827 ms 25176 KB Output is correct
15 Correct 823 ms 25176 KB Output is correct

Subtask #2
2.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1167 ms 25176 KB Output isn't correct
2 Correct 1324 ms 25176 KB Output is correct
3 Execution timed out 1500 ms 25176 KB Program timed out
4 Execution timed out 1500 ms 25176 KB Program timed out
5 Execution timed out 1500 ms 25304 KB Program timed out
6 Execution timed out 1500 ms 25436 KB Program timed out
7 Execution timed out 1500 ms 25304 KB Program timed out
8 Execution timed out 1500 ms 25304 KB Program timed out
9 Execution timed out 1500 ms 25304 KB Program timed out
10 Execution timed out 1500 ms 25304 KB Program timed out

Subtask #3
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1500 ms 29528 KB Program timed out
2 Execution timed out 1500 ms 29680 KB Program timed out
3 Execution timed out 1500 ms 28736 KB Program timed out
4 Execution timed out 1500 ms 28868 KB Program timed out
5 Execution timed out 1500 ms 28868 KB Program timed out
6 Execution timed out 1500 ms 33384 KB Program timed out
7 Execution timed out 1500 ms 31564 KB Program timed out
8 Execution timed out 1500 ms 32432 KB Program timed out
9 Execution timed out 1500 ms 32564 KB Program timed out
10 Execution timed out 1500 ms 32960 KB Program timed out
11 Execution timed out 1500 ms 34764 KB Program timed out
12 Execution timed out 1500 ms 35144 KB Program timed out