oj.uz

Submission #166835

# Submission time Handle Problem Language Result Execution time Memory
166835 2019-12-04T08:51:00 Z Trickster Shymbulak (IZhO14_shymbulak) C++14
0 / 100
 1500 ms 207008 KB 
//Suleyman Atayew

#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>

#define N 5010
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define inf 1000000007
#define pii pair <ll, ll>

using namespace std;

int n;
int a, b;
int v[N][N];
vector <int> E[N];

int main()
{
	scanf("%d", &n);
	
	for(ll i = 1; i <= n; i++) {
		scanf("%d%d", &a, &b);
		
		E[a].pb(b);
		E[b].pb(a);
	}
	
	for(ll i = 1; i <= n; i++)
		for(ll h = 1; h <= n; h++)
			v[i][h] = 1e9;
	
	for(ll i = 1; i <= n; i++) {
		queue <ll> Q;
		Q.push(i);
		
		v[i][i] = 0;
		
		while(!Q.empty()) {
			ll x = Q.front();
			Q.pop();
			
			for(auto h: E[x])
				if(v[i][h] == 1e9) {
					v[i][h] = v[i][x] + 1;
					Q.push(h);
				}
		}
	}
	
	int mx = 0;
	for(ll i = 1; i <= n; i++)
		for(ll h = 1; h <= n; h++)
			mx = max(mx, v[i][h]);
	
	vector <pii> A;
	for(ll i = 1; i <= n; i++)
		for(ll h = i; h <= n; h++)
			if(mx == v[i][h])
				A.pb({i, h});
	
	ll ans = 0;
	for(auto i: A) {
		ll a = i.ff, b = i.ss;
		
		queue <ll> Q;
		Q.push(b);
		
		ll arr[N];
		ll vis[N];
		memset(arr, 0, sizeof(arr));
		memset(vis, 0, sizeof(vis));
		
		while(!Q.empty()) {
			ll x = Q.front();
			Q.pop();
			
			for(auto h: E[x])
				if(v[a][h] == v[a][x]-1 && vis[h] == 0)
					arr[v[a][h]]++, Q.push(h), vis[h] = 1;
		}
		
		ll sum = 1;
		for(ll h = 0; h < mx; h++) sum *= arr[h];
		
		ans += sum;
	}
	printf("%lld", ans);
}

Compilation message

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
shymbulak.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Incorrect 2 ms 632 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5368 KB Output is correct
2 Execution timed out 1566 ms 14560 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 527 ms 207008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -