oj.uz

Submission #340660

# Submission time Handle Problem Language Result Execution time Memory
340660 2020-12-28T05:41:46 Z tengiz05 Shymbulak (IZhO14_shymbulak) C++17
30 / 100
 1500 ms 14920 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 = 2e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int a[N], n, m, k;
vector<int> edges[N];
int max_distance = 0;
int answer = 0;
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++){
		queue<int> q;
		q.push(start);
		vector<int> dist(n+1, 0);
		vector<bool> used(n+1, false);
		vector<int> par[n+1];
		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].pb(u);
					used[v] = true;
					q.push(v);
					dist[v] = dist[u] + 1;
				}else if(dist[v] == dist[u] + 1){
					par[v].pb(u);
				}
			}
		}
		for(i=1;i<=n;i++){
			if(chmax(max_distance, dist[i]))
				answer = 0;
		}
		vector<int> dp(n+1);
		dp[start] = 1;
		for(auto u : order){
			for(auto v : edges[u]){
				if(find(all(par[u]), v) == par[u].end())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';
		
	}
	assert(answer%2==0);
	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:21:9: warning: unused variable 'j' [-Wunused-variable]
   21 |  int i, j;
      |         ^

Subtask #1
30.0 / 30.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 5100 KB Output is correct
2 Correct 63 ms 5184 KB Output is correct
3 Correct 110 ms 5108 KB Output is correct
4 Correct 115 ms 5100 KB Output is correct
5 Execution timed out 1582 ms 5484 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1583 ms 14920 KB Time limit exceeded
2 Halted 0 ms 0 KB -