Submission #1101513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101513		jacklog	Hotspot (NOI17_hotspot)	C++17	9 / 100	2 ms	592 KiB

hotspot

#include <bits/stdc++.h>
using namespace std;

const int N = 5e3 + 10;

int n, m, k;
vector <int> g[N];
int a[N], b[N];

namespace subtask34 {
	int h[N], p[N][25];
	int cnt[N];

	void DFS(int i, int par) {
		for (auto v : g[i]) {
			if(v == par) 
				continue;
			h[v] = h[i] + 1;
			p[v][0] = i;
			DFS(v, i);
		}
	}

	int lca(int u, int v) {
		if(h[u] < h[v]) swap(u, v);
		for (int i = 20; i >= 0; i--) {
			if(h[p[u][i]] >= h[v]) 
				u = p[u][i];
		}
		if(u == v) return u;
		for (int i = 20; i >= 0; i--) {
			if(p[u][i] != p[v][i])
				u = p[u][i], v = p[v][i];
		}
		return p[u][0];
	}

	int lca_uv;
	bool DFS2(int i, int par) {
		// cout << i << " ";
		if(i == lca_uv) {
			cnt[i]++;
			return true;
		}
		bool check = false;
		for (auto v : g[i]) {
			if(v == par) 
				continue;
			check = DFS2(v, i);
			if(check) break;
		}

		if(check)
			cnt[i]++;
		return check;
	}
	void solve() {
		h[1] = 1;
		DFS(1, -1);
		for (int j = 1; j <= 20; j++)
			for (int i = 1; i <= n; i++)
				p[i][j] = p[ p[i][j - 1] ][j - 1];

		for (int i = 1; i <= k; i++) {
			int u = a[i], v = b[i];
			lca_uv = lca(u, v);
			// cout << u << " " << v << " " << lca_uv << endl;
			DFS2(u, -1);
			DFS2(v, -1);
			cnt[lca_uv]--;
			// cout << "\n";
		}
		
		int maxi = 0, ans = -1;
		for (int i = 1; i <= n; i++) {
			if(cnt[i] > maxi) {
				maxi = cnt[i];
				ans = i;
			}
		}
		// for (int i = 1; i <= n; i++) {
		// 	cout << cnt[i] << " ";
		// }
		cout << ans;
	}
}

namespace subtask5 {
	
	void solve() {

	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	cin >> k;
	for (int i = 1; i <= k; i++) 
		cin >> a[i] >> b[i];
	if(k == 1 and m == n - 1) cout << a[1];
	else if(m == n - 1) subtask34::solve();
	else if(n <= 1000 and m <= 8000 and k <= 20) subtask5::solve();
}

/*
subtask 5:
Đặc điểm: k <= 20
n <= 1000, m <= 8000
Ei(w) = count(dist(a, b) qua w) / count(dist(a, b))

cost edge = 1 => BFS
Tìm dist(A, B) => đếm số đường đi từ A -> B
có tối đa bao nhiêu đường, nó sẽ tối ưu thế nào?


Sol 1 : 
Đi đếm toàn bộ đường đi ? (có vẻ khả thi)
đồ thị sẽ có dạng: bắt đầu tại A kết thúc tại B,

A -> ... -> B
E[i][w] = Ei(w)
Find i that sigma(E[1 -> k][i]) is max
Dùng truy vết ngược (O(n))
O(k * n)
*/

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 18
• Subtask 5: 0 / 26
• Subtask 6: 0 / 36