oj.uz

Submission #17962

# Submission time Handle Problem Language Result Execution time Memory
17962 2016-01-13T09:57:12 Z Adilkhan Shymbulak (IZhO14_shymbulak) C++
46 / 100
 693 ms 202788 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 = 5000;
const ll INF = (ll)(1e9);
const ll mod = (ll)(1e9) + 7;
const double eps = 1e-9;

int d[N][N][2], n, m, mx, sum;
        
vector <int> v[N];

queue <int> q;

void fmbfs(int s) {               
	for (int i = 1; i <= n; ++i) d[s][i][1] = 0, d[s][i][0] = -1;
	q.push(s);
	d[s][s][0] = 0; d[s][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[s][to][0] == -1) {
				d[s][to][0] = d[s][x][0] + 1;
				d[s][to][1] += d[s][x][1];
				q.push(to);			
				continue;
			}		
			if (d[s][to][0] == d[s][x][0] + 1) {
				d[s][to][1] += d[s][x][1];
			}
		}	
	}	
	for (int i = 1; i <= n; ++i) {
		mx = max(mx, d[s][i][0]);
	}         
}

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) {
		for (int j = i + 1; j <= n; ++j) {
			if (d[i][j][0] == mx) {
				sum += d[i][j][1];			
			}		
		}
	}
	printf("%lld", sum);   
	return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
16.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 197156 KB Output is correct
2 Correct 3 ms 197156 KB Output is correct
3 Correct 16 ms 197156 KB Output is correct
4 Correct 15 ms 197156 KB Output is correct
5 Correct 598 ms 197288 KB Output is correct
6 Runtime error 0 ms 197152 KB SIGSEGV Segmentation fault
7 Correct 693 ms 197288 KB Output is correct
8 Correct 673 ms 197288 KB Output is correct
9 Runtime error 0 ms 197284 KB SIGSEGV Segmentation fault
10 Correct 652 ms 197288 KB Output is correct

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 198076 KB SIGSEGV Segmentation fault
2 Runtime error 31 ms 199792 KB SIGSEGV Segmentation fault
3 Runtime error 0 ms 197284 KB SIGSEGV Segmentation fault
4 Runtime error 0 ms 197284 KB SIGSEGV Segmentation fault
5 Runtime error 1 ms 197284 KB SIGSEGV Segmentation fault
6 Runtime error 18 ms 199132 KB SIGSEGV Segmentation fault
7 Runtime error 51 ms 201112 KB SIGSEGV Segmentation fault
8 Runtime error 0 ms 197284 KB SIGSEGV Segmentation fault
9 Runtime error 0 ms 197284 KB SIGSEGV Segmentation fault
10 Runtime error 0 ms 197284 KB SIGSEGV Segmentation fault
11 Runtime error 53 ms 201364 KB SIGSEGV Segmentation fault
12 Runtime error 37 ms 202788 KB SIGSEGV Segmentation fault