QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#197791 | #7513. Palindromic Beads | ucup-team484 | WA | 9ms | 36788kb | C++17 | 3.3kb | 2023-10-02 19:56:42 | 2023-10-02 19:56:42 |
Judging History
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'