Submission #340660

#	Time	Username	Problem	Language	Result	Execution time	Memory
340660		tengiz05	Shymbulak (IZhO14_shymbulak)	C++17	30 / 100	1583 ms	14920 KiB

shymbulak

#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 (stderr)

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

• Subtask 1: 30 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50