QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#288488 | #5669. Traveling in Jade City | VinhLuu | WA | 4ms | 24832kb | C++23 | 6.9kb | 2023-12-22 19:16:52 | 2023-12-22 19:16:52 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 2e5 + 5;
struct node{
int lz, lzg, t, mx;
} st[N << 2];
int n, q, T[N], R[N], k[N], d[N], kq[N], in[N], out[N], demin, en[N], f[N][22], demout;
vector<int> p[N], vr[N], g[N];
void build(int i,int l,int r){
if(l == r){
st[i].lzg = -1,
st[i].t = 1;
st[i].mx = d[T[l]];
return ;
}
int mid = (l + r) >> 1;
build(i << 1, l, mid);
build(i << 1|1, mid + 1, r);
st[i].t = st[i << 1]. t + st[i << 1|1].t;
st[i].mx = max(st[i << 1].mx, st[i << 1|1].mx);
st[i].lzg = -1;
}
void dolz(int i){
if(st[i].lz == 0) return;
int x = st[i].lz;
st[i].lz = 0;
st[i << 1].mx += x;
st[i << 1|1].mx += x;
st[i << 1].lz += x;
st[i << 1|1].lz += x;
}
void dolzg(int i,int l,int r){
int mid = (l + r) >> 1;
if(st[i].lzg == -1) return;
int x = st[i].lzg;
st[i].lzg = -1;
if(x == 0){
st[i << 1].lzg = x;
st[i << 1|1].lzg = x;
st[i << 1].t = 0;
st[i << 1|1].t = 0;
}else{
st[i << 1].lzg = x;
st[i << 1|1].lzg = x;
st[i << 1].t = mid - l + 1;
st[i << 1|1].t = r - mid;
}
}
void update(int i,int l,int r,int u,int v,int x){
if(l > r || l > v || r < u) return;
if(u <= l && r <= v){
st[i].lz += x;
st[i].mx += x;
// cout << i << " " << l << " " << r << " " << x << " query\n";
return;
}
dolz(i);
dolzg(i,l,r);
int mid = (l + r) >> 1;
update(i << 1, l, mid, u, v, x);
update(i << 1|1, mid + 1, r, u, v, x);
st[i].t = st[i << 1]. t + st[i << 1|1].t;
st[i].mx = max(st[i << 1].mx, st[i << 1|1].mx);
}
int ret;
void get(int i,int l,int r){
if(st[i].t == 0 || l > r) return;
// cout << l << " " << r << " " << st[i].t << " vist\n";
// for(int j = l; j <= r; j ++) cout << T[j] << " ";
// cout << "\n";
if(st[i].t == (r - l + 1)){
// cout << st[i].mx << " w\n";
ret = max(ret, st[i].mx);
return;
}
dolz(i);
dolzg(i,l,r);
int mid = (l + r) >> 1;
if(st[i << 1].t != 0 && l <= mid) get(i << 1, l, mid);
if(st[i << 1|1].t != 0 && mid + 1 <= r) get(i << 1|1, mid + 1, r);
st[i].t = st[i << 1]. t + st[i << 1|1].t;
st[i].mx = max(st[i << 1].mx, st[i << 1|1].mx);
}
void gan(int i,int l,int r,int u,int v,int x){
if(l > r || l > v || r < u) return;
if(u <= l && r <= v){
if(x == 0){
st[i].t = 0;
st[i].lzg = 0;
}else{
st[i].t = r - l + 1;
st[i].lzg = 1;
}
return;
}
dolz(i);
dolzg(i,l,r);
int mid = (l + r) >> 1;
gan(i << 1, l, mid, u, v, x);
gan(i << 1|1, mid + 1, r, u, v, x);
st[i].t = st[i << 1]. t + st[i << 1|1].t;
st[i].mx = max(st[i << 1].mx, st[i << 1|1].mx);
}
int tv(int i,int l,int r,int u){
if(l > u || r < u) return 0;
if(l == r) return st[i].mx;
int mid = (l + r) >> 1;
dolz(i);
dolzg(i,l,r);
return tv(i << 1, l, mid, u) + tv(i << 1|1, mid + 1, r, u);
}
int tv2(int i,int l,int r,int u){
if(l > u || r < u) return 0;
if(l == r) return st[i].t;
int mid = (l + r) >> 1;
dolz(i);
dolzg(i,l,r);
return tv2(i << 1, l, mid, u) + tv2(i << 1|1, mid + 1, r, u);
}
int pa[N];
void dfs(int u,int v){
in[u] = ++demin;
T[demin] = u;
if(u == 1) for(int i = 0; i <= 18; i ++) f[u][i] = u;
else{
f[u][0] = v;
for(int i = 1; i <= 18; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
}
for(auto j : p[u]){
if(j == v) continue;
d[j] = d[u] + 1;
pa[j] = u;
dfs(j, u);
}
out[u] = ++demout;
en[u] = demin;
}
bool kt(int u,int v){
return in[u] <= in[v] && out[u] >= out[v];
}
int FIND(int x,int u){
int what = u;
for(int i = 18; i >= 0; i --){
if(kt(x, f[u][i]) && f[u][i] != x){
what = f[u][i];
u = f[u][i];
}
}
return what;
}
void cal(int u,int v){
// cout << u << " :\n";
// if(u == 4) for(int i = 1; i <= n; i ++) cout << i << " " << tv(1, 1, n, in[i]) << " lee\n";
for(auto j : g[u]){
// cout << j << " u\n";
for(auto x : vr[j]){
// cout << x << "w\n";
if(kt(x, u)){
// cout << " cha\n";
int lmao = FIND(x, u);
// for(auto y : p[x]) if(y != pa[x] && kt(y, u)) lmao = y;
gan(1, 1, n, 1, in[lmao] - 1, 0);
gan(1, 1, n, en[lmao] + 1, n, 0);
// cout << lmao << " " << x << " " << 1 << " " << in[lmao] << " " << en[u] + 1 << " " << n << "q\n";
}else{
// cout << " con\n";
gan(1, 1, n, in[x], en[x], 0);
// cout << in[x] << " " << en[x] << " q\n";
}
}
// for(int i = 1; i <= n; i ++) cout << i << " " << tv2(1, 1, n, in[i]) << " l\n";
// for(int i = 1; i <= n; i ++) cout << T[i] << " ";
// cout << "\n";
// for(int i = 1; i <= n; i ++) cout << i << " " << in[i] << " m\n";
ret = 0;
get(1, 1, n);
kq[j] = ret;
gan(1, 1, n, 1, n, 1);
}
for(auto j : p[u]){
if(j == v) continue;
update(1, 1, n, in[j], en[j], -1);
update(1, 1, n, 1, in[j] - 1, 1);
update(1, 1, n, en[j] + 1, n, 1);
// cout << u << " " << j << " " << "kt\n";
cal(j, u);
update(1, 1, n, in[j], en[j], 1);
update(1, 1, n, 1, in[j] - 1, -1);
update(1, 1, n, en[j] + 1, n, -1);
}
}
void sub3(){
dfs(1, 0);
build(1, 1, n);
for(int i = 1; i <= q; i ++){
cin >> R[i] >> k[i];
for(int j = 1; j <= k[i]; j ++){
int x; cin >> x;
vr[i].pb(x);
}
g[R[i]].pb(i);
}
cal(1, 0);
for(int i = 1; i <= q; i ++) cout << kq[i] << "\n";
}
bool fl[5005];
void go(int u,int v,int dis){
ret = max(ret, dis);
for(auto j : p[u]){
if(j == v || fl[j] == false) continue;
go(j, u, dis + 1);
}
}
void sub1(){
for(int i = 1; i <= q; i ++){
cin >> R[i] >> k[i];
for(int j = 1; j <= n; j ++) fl[j] = true;
for(int j = 1; j <= k[i]; j ++){
int x; cin >> x;
fl[x] = false;
}
ret = 0;
go(R[i], 0, 0);
cout << ret << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen("lpath.inp","r")){
freopen("lpath.inp","r",stdin);
freopen("lpath.out","w",stdout);
}
cin >> n >> q;
for(int i = 1; i < n; i ++){
int x, y; cin >> x >> y;
p[x].pb(y);
p[y].pb(x);
}
// if(n <= 5000 && q <= 5000) sub1();
// else
sub3();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 24832kb
input:
4 3 1 9 2 3 8 4 1 1 q 3 4 x 0 q 3 4 c 3 q 3 4 c 1 q 3 4 x 0 q 3 4
output:
1 0 0
result:
wrong answer 1st lines differ - expected: '6', found: '1'