제출 #340674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
340674		tengiz05	관광지 (IZhO14_shymbulak)	C++17	30 / 100	1593 ms	748 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 = 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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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