QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#198596 | #7513. Palindromic Beads | mendicillin2 | WA | 777ms | 246300kb | C++17 | 5.8kb | 2023-10-03 15:12:00 | 2023-10-03 15:12:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = int(a); i < int(b); i++)
#define per(i, a, b) for (int i = int(b)-1; i >= int(a); i--)
#define trav(a, x) for (auto& a : x)
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;
using ll = int64_t;
using vi = vc<int>;
using pii = pair<int, int>;
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
template <class F>
struct ycr {
F f;
template <class T> explicit ycr(T&& ff) : f(forward<T>(ff)) {}
template <class... A> decltype(auto) operator()(A&&... args) {
return f(ref(*this), forward<A>(args)...);
}
};
template <class F> decltype(auto) yc(F&& f) {
return ycr<decay_t<F>>(forward<F>(f));
}
struct GC {
char buf[1<<16];
size_t s=0,e=0;
char operator()(){
if(s>=e){
buf[0]=0;
s=0;
e=fread(buf,1,sizeof(buf),stdin);
}
return buf[s++];
}
} gc;
int read() {
char c;
while((c=gc())<40);
if(c==-'-')return -read();
int a=c-'0';
while(isdigit(c=gc()))a=a*10+c-'0';
return a;
}
struct hldecomp {
int n;
vi ord;
vc<array<int,2>> idx;
vc<pair<int,int>> heavy;
hldecomp():n(0){}
hldecomp(const vi&par):n(sz(par)),ord(n),idx(n),heavy(n){
vvc<int> ch(n);
for (int i = 0; i < n; i++) {
if (par[i] != -1) {
ch[par[i]].push_back(i);
}
}
vi s(n);
int nidx = 0;
for (int i = 0; i < n; i++) {
if (par[i] != -1) continue;
yc([&](auto self, int v) -> void {
s[v] = 1;
for (int w : ch[v]) {
self(w);
s[v] += s[w];
}
if (!ch[v].empty()) {
auto mit = max_element(ch[v].begin(), ch[v].end(), [&](int a, int b) {
return s[a] < s[b];
});
swap(*ch[v].begin(), *mit);
}
})(i);
yc([&](auto self, int v, bool rt = true) -> void {
ord[idx[v][0] = nidx++] = v;
if (rt) {
heavy[idx[v][0]] = {par[v] == -1 ? -1 : idx[par[v]][0], 1};
} else {
assert(idx[par[v]][0] == idx[v][0]-1);
heavy[idx[v][0]] = heavy[idx[v][0]-1];
heavy[idx[v][0]].second++;
}
bool crt = false;
for (int w : ch[v]) {
self(w, crt);
crt = true;
}
idx[v][1] = nidx;
})(i);
}
assert(n == nidx);
}
int lca(int a, int b) {
a = idx[a][0], b = idx[b][0];
while (true) {
if (a > b) swap(a, b);
assert(a <= b);
if (a > b - heavy[b].second) {
return ord[a];
}
b = heavy[b].first;
if (b == -1) return -1;
}
}
bool in_subtree(int a, int p) const {
return idx[p][0] <= idx[a][0] &&
idx[a][1] <= idx[p][1];
}
};
const int MAXV = 2.5e7;
struct seg {
array<int, 2> c;
int v;
} pool[MAXV];
template <class T> void setmax(T& a, const T& b) {
if (a < b) a = b;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(20);
int N;
cin >> N;
vector<vector<int>> locs(N);
for (int i = 0; i < N; i++) {
int c;
cin >> c;
c--;
locs[c].push_back(i);
}
vector<vector<int>> adj(N);
for (int e = 0; e < N-1; e++) {
int a, b;
cin >> a >> b;
a--, b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
vector<int> par(N, -1);
vector<int> depth(N, 0);
yc([&](auto self, int cur, int prv, int d) -> void {
par[cur] = prv;
depth[cur] = d;
for (int nxt : adj[cur]) {
if (nxt == prv) continue;
self(nxt, cur, d+1);
}
})(0, -1, 0);
auto hld = hldecomp(par);
vector<tuple<int, int, int>> stuff;
stuff.reserve(N/2);
for (int c = 0; c < N; c++) {
if (locs[c].size() <= 1) continue;
assert(locs[c].size() == 2);
int x = locs[c][0];
int y = locs[c][1];
int a = hld.lca(x, y);
int d = depth[x] + depth[y] - 2 * depth[a];
stuff.emplace_back(d, x, y);
}
const int S = 1 << (N <= 1 ? 0 : 32 - __builtin_clz(N-1));
vector<int> seg(2*S);
int V = 1;
auto upd_inner = [&](int& rt, int k, int v) -> void {
yc([&](auto self, int& a, int l, int r) -> void {
if (!a) {
assert(V < MAXV);
a = V++;
pool[a].c = {0,0};
pool[a].v = 0;
}
assert(a);
setmax(pool[a].v, v);
if (r-l == 1) {
return;
}
int m = (l+r)/2;
if (k < m) {
self(pool[a].c[0], l, m);
assert(pool[a].c[0]);
} else {
self(pool[a].c[1], m, r);
assert(pool[a].c[1]);
}
assert(pool[a].v >= v);
})(rt, 0, S);
};
auto upd_outer = [&](int x, int y, int v) -> void {
assert(0 <= x && x < S);
assert(0 <= y && y < S);
for (int a = S+x; a >= 1; a /= 2) {
upd_inner(seg[a], y, v);
assert(seg[a]);
}
};
auto query_inner = [&](int rt, int ql, int qr) -> int {
return yc([&](auto self, int a, int l, int r) -> int {
if (!a) return 0;
if (r <= ql || qr <= l) return 0;
if (ql <= l && r <= qr) {
return pool[a].v;
}
int m = (l+r)/2;
return max(self(pool[a].c[0], l, m), self(pool[a].c[1], m, r));
})(rt, 0, S);
};
auto query_outer = [&](int xl, int xr, int yl, int yr) -> int {
assert(0 <= xl);
assert(xl <= xr);
assert(xr <= yl);
assert(yl <= yr);
assert(yr <= S);
if (xl == xr) return 0;
if (yl == yr) return 0;
int res = 0;
for (int a = S+xl, b = S+xr; a < b; a /= 2, b /= 2) {
if (a & 1) setmax(res, query_inner(seg[a++], yl, yr));
if (b & 1) setmax(res, query_inner(seg[--b], yl, yr));
}
return res;
};
const auto& idx = hld.idx;
sort(stuff.begin(), stuff.end());
reverse(stuff.begin(), stuff.end());
int ans = 1;
for (auto [d, x, y] : stuff) {
assert(x != y);
int v;
if (idx[x][0] > idx[y][0]) swap(x, y);
int a = hld.lca(x, y);
if (a != x) {
v = query_outer(idx[x][0], idx[x][1], idx[y][0], idx[y][1]);
} else {
int c = -1;
for (int z : adj[x]) {
if (hld.in_subtree(y, z)) {
c = z;
break;
}
}
assert(c != -1);
v = query_outer(0, idx[c][0], idx[y][0], idx[y][1]);
setmax(v, query_outer(idx[y][0], idx[y][1], idx[c][1], N));
}
v += 2;
setmax(ans, v + int(d >= 2));
upd_outer(idx[x][0], idx[y][0], v);
}
cout << ans << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3580kb
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: 1ms
memory: 3540kb
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: 1ms
memory: 3468kb
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: 0
Accepted
time: 0ms
memory: 3544kb
input:
6 1 2 3 4 5 6 1 2 2 3 3 4 4 5 5 6
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 5992kb
input:
2000 845 1171 345 282 1181 625 754 289 681 493 423 840 1494 318 266 1267 967 379 135 14 39 191 60 972 116 1216 1205 19 194 185 1360 861 379 430 1262 1151 756 65 389 488 277 53 1283 1438 101 1465 195 714 737 980 80 298 961 1326 163 1163 1317 1152 992 35 334 802 1502 486 710 234 555 88 1278 146 46 696...
output:
5
result:
ok single line: '5'
Test #6:
score: 0
Accepted
time: 471ms
memory: 238912kb
input:
200000 48015 47923 20609 71806 43752 68214 95683 89449 25809 58110 19878 52931 7845 45206 86245 82945 62977 37876 12456 105915 10509 92943 66950 88545 26442 26545 42278 66977 3970 9631 21524 43638 7979 58240 25719 56260 276 89721 9553 16550 52161 30307 82748 108443 36676 48581 59069 57412 62453 7965...
output:
5
result:
ok single line: '5'
Test #7:
score: 0
Accepted
time: 433ms
memory: 240644kb
input:
200000 13011 51198 65374 107045 66506 14385 35784 94265 71449 41817 24646 60714 53382 68358 9354 840 3139 71282 72215 69550 2121 41498 13675 76444 67690 40513 56439 12832 51976 35333 47208 59602 98993 9383 77866 10464 41517 89125 58804 91741 66160 74208 70991 63865 84870 14282 2441 78046 73372 36311...
output:
7
result:
ok single line: '7'
Test #8:
score: 0
Accepted
time: 458ms
memory: 240924kb
input:
200000 38715 33241 65919 39407 27500 36200 2259 42301 79147 57505 20 81399 69499 23658 14534 86934 14352 69558 59763 43318 35360 3281 38188 40058 40571 103709 75625 8434 53802 87159 98628 69421 53711 47986 18350 6079 37362 39377 71936 89573 25983 66882 48999 58918 66432 17453 82515 9588 95375 87287 ...
output:
45
result:
ok single line: '45'
Test #9:
score: 0
Accepted
time: 517ms
memory: 241304kb
input:
200000 36449 57574 3145 38591 832 17710 66613 78947 27635 83275 89878 48329 94614 584 96832 9321 72046 44873 5396 61452 63224 63740 26579 13706 108490 19092 89439 85884 12016 5105 48638 74004 41569 35006 22276 45609 25350 49906 35479 15875 68938 77699 48828 21628 11242 77040 70838 45771 27704 64865 ...
output:
135
result:
ok single line: '135'
Test #10:
score: 0
Accepted
time: 702ms
memory: 243436kb
input:
200000 13528 65006 30352 8565 36687 6748 5507 44320 7189 17847 46996 82728 102722 4727 36914 74228 21460 87970 11733 47170 67282 104558 66436 64504 57055 88619 42995 25569 101298 90984 76491 51994 62257 103424 8221 69668 99170 6808 29043 73058 5277 26614 23654 25152 64939 38418 78518 5330 37531 4305...
output:
425
result:
ok single line: '425'
Test #11:
score: -100
Wrong Answer
time: 777ms
memory: 246300kb
input:
200000 92279 5566 62695 50240 45387 51097 57743 94873 53220 29260 72584 38043 86335 33441 12946 30267 12932 18258 4560 8896 64393 39608 53183 34285 36518 18501 51940 8658 101018 48522 21336 104735 25785 73132 33489 81905 94563 18128 87872 24765 54563 57218 61869 50458 75919 63764 48155 4489 35212 44...
output:
835
result:
wrong answer 1st lines differ - expected: '839', found: '835'