QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#197791#7513. Palindromic Beadsucup-team484WA 9ms36788kbC++173.3kb2023-10-02 19:56:422023-10-02 19:56:42

Judging History

你现在查看的是最新测评结果

  • [2024-03-27 16:34:54]
  • hack成功,自动添加数据
  • (/hack/584)
  • [2024-03-27 16:18:45]
  • hack成功,自动添加数据
  • (/hack/583)
  • [2023-10-02 19:56:42]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:36788kb
  • [2023-10-02 19:56:42]
  • 提交

answer

#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define st first
#define nd second
#define pii pair<int, int>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
const int M = 1e7 + 5;
vector<int> adj[N];
int fi[N], la[N], par[N], curt = 0;
int root[N], n, L[M], R[M], seg[M], nodecnt = 0;

void dfs(int u, int p) {
	par[u] = p;
	fi[u] = curt++;
	for (int v: adj[u]) {
		if (v == p) continue;
		dfs(v, u);
	}
	la[u] = curt - 1;
}

int qry2(int l, int r, int& k, int yl, int yr) {
	if (r < yl || yr < l || !k) return 0;
	if (yl <= l && r <= yr) return seg[k];
	int m = (l + r) / 2;
	return max(qry2(l, m, L[k], yl, yr), qry2(m + 1, r, R[k], yl, yr));
}

int qry(int l, int r, int k, int xl, int xr, int yl, int yr) {
	if (r < xl || xr < l || xl > xr || yl > yr) return 0;
	if (xl <= l && r <= xr) return qry2(0, n - 1, root[k], yl, yr);
	int m = (l + r) / 2;
	return max(qry(l, m, 2 * k, xl, xr, yl, yr), qry(m + 1, r, 2 * k + 1, xl, xr, yl, yr));
}

void upd2(int l, int r, int& k, int y, int v) {
	if (r < y || y < l) return;
	if (!k) k = ++nodecnt;
	seg[k] = max(seg[k], v);
	if (y <= l && r <= y) return;
	int m = (l + r) / 2;
	upd2(l, m, L[k], y, v);
	upd2(m + 1, r, R[k], y, v);
}

void upd(int l, int r, int k, int x, int y, int v) {
	if (r < x || x < l) return;
	upd2(0, n - 1, root[k], y, v);
	if (x <= l && r <= x) return;
	int m = (l + r) / 2;
	upd(l, m, k * 2, x, y, v);
	upd(m + 1, r, k * 2 + 1, x, y, v);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	vector<int> c(n), deg(n), dp(n);
	vector<vector<int>> pos(n);
	for (int i = 0; i < n; i++)
		cin >> c[i], c[i]--, pos[c[i]].push_back(i);
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v; u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int it = 0; it < 2; it++) {
		deque<int> pq;
		int ce = 0;
		for (int i = 0; i < n; i++) {
			deg[i] = sz(adj[i]);
			if (deg[i] == 1)
				pq.push_back(i);
		}
		while (!pq.empty()) {
			int u = pq.front(); pq.pop_front();
			for (int v: adj[u])
				if (--deg[v] == 1)
					pq.push_back(v);
			ce = u;
			if (sz(pos[c[u]]) == 1 || dp[c[u]] != 0 || it == 0)
				continue;
			int x = pos[c[u]][0], y = pos[c[u]][1];
			if (fi[x] <= fi[y] && la[y] <= la[x] || fi[y] <= fi[x] && la[x] <= la[y]) {
				if (fi[y] <= fi[x] && la[x] <= la[y])
					swap(x, y);
				for (int v: adj[x])
					if (fi[v] <= fi[y] && la[y] <= la[v] && v != par[x]) {
						int v1 = max(qry(0, n - 1, 1, 0, fi[v] - 1, fi[y], la[y]), qry(0, n - 1, 1, la[v] + 1, curt - 1, fi[y], la[y]));
						int v2 = max(qry(0, n - 1, 1, fi[y], la[y], 0, fi[v] - 1), qry(0, n - 1, 1, fi[y], la[y], la[v] + 1, curt - 1));
						dp[c[u]] = max(v1, v2) + 2;
					}
			} else
				dp[c[u]] = max(qry(0, n - 1, 1, fi[x], la[x], fi[y], la[y]), qry(0, n - 1, 1, fi[y], la[y], fi[x], la[x])) + 2;
			upd(0, n - 1, 1, fi[x], fi[y], dp[c[u]]);
		}
		if (it == 0)
			dfs(ce, -1);
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ans = max(ans, dp[c[i]]);
//		cout << i << " " << dp[c[i]] << "\n";
		if (sz(pos[c[i]]) == 1)
			continue;
		int x = pos[c[i]][0], y = pos[c[i]][1], o = 0;
		for (int v: adj[x])
			o |= v == y;
		if (o == 0)
			ans = max(ans, dp[c[i]] + 1);
	}
	cout << ans << "\n";
}

详细

Test #1:

score: 100
Accepted
time: 9ms
memory: 36648kb

input:

4
1 1 2 2
1 2
2 3
2 4

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 0ms
memory: 36788kb

input:

5
1 3 2 2 1
1 2
2 3
3 4
4 5

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 0ms
memory: 36100kb

input:

6
1 1 2 2 3 3
1 2
2 3
3 4
4 5
5 6

output:

2

result:

ok single line: '2'

Test #4:

score: -100
Wrong Answer
time: 6ms
memory: 36620kb

input:

6
1 2 3 4 5 6
1 2
2 3
3 4
4 5
5 6

output:

0

result:

wrong answer 1st lines differ - expected: '1', found: '0'