oj.uz

Submission #340674

# Submission time Handle Problem Language Result Execution time Memory
340674 2020-12-28T06:00:01 Z tengiz05 Shymbulak (IZhO14_shymbulak) C++17
30 / 100
 1500 ms 748 KB 
#include <bits/stdc++.h>
using namespace std;
//~ #define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> bool chmin(T& a, const T& b) {return a>b? a=b, true:false;}
template<class T> bool chmax(T& a, const T& b) {return a<b? a=b, true:false;}
const int mod = 1e9+7, N = 5005;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int n, m, k;
vector<int> edges[N];
int max_distance = 0;
int answer = 0;
int par[N][2];
bool used[N];
int dist[N], dp[N];
void solve(int test_case){
	int i, j;
	cin >> n;
	for(i=0;i<n;i++){
		int u, v;
		cin >> u >> v;
		edges[u].pb(v);
		edges[v].pb(u);
	}
	for(int start=1;start<=n;start++){
		for(i=1;i<=n;i++){
			memset(used, false, sizeof used);
			memset(dp, 0, sizeof dp);
			memset(par, 0, sizeof par);
			memset(dist, 0, sizeof dist);
		}
		queue<int> q;
		q.push(start);
		used[start] = true;
		vector<int> order;
		while(!q.empty()){
			auto u = q.front();q.pop();
			order.pb(u);
			for(auto v : edges[u]){
				if(!used[v]){
					par[v][0] = u;
					used[v] = true;
					q.push(v);
					dist[v] = dist[u] + 1;
				}else if(dist[v] == dist[u] + 1){
					par[v][1] = u;
				}
			}
		}
		for(i=1;i<=n;i++){
			if(chmax(max_distance, dist[i]))
				answer = 0;
		}
		dp[start] = 1;
		for(auto u : order){
			for(auto v : edges[u]){
				if(par[u][0] != v && par[u][1] != v)continue;
				dp[u] += dp[v];
			}if(dist[u] == max_distance)answer += dp[u];
		}
		//~ cout << "\n\n";
		//~ for(i=1;i<=n;i++)cout << dist[i] << ' ';cout << '\n';
		
		//~ for(i=1;i<=n;i++)cout << dp[i] << ' ';cout << '\n';
		//~ cout << "when start was " << start << " they were: " << max_distance << ' ' << answer << '\n';
		
	}
	cout << answer/2 << '\n';
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int _T;
	cin >> _T;
	for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message

shymbulak.cpp: In function 'void solve(int)':
shymbulak.cpp:24:9: warning: unused variable 'j' [-Wunused-variable]
   24 |  int i, j;
      |         ^

Subtask #1
30.0 / 30.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1460 ms 628 KB Output is correct
2 Execution timed out 1593 ms 620 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

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