QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#288488#5669. Traveling in Jade CityVinhLuuWA 4ms24832kbC++236.9kb2023-12-22 19:16:522023-12-22 19:16:52

Judging History

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

  • [2023-12-22 19:16:52]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:24832kb
  • [2023-12-22 19:16:52]
  • 提交

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();

}

詳細信息

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'