Submission #1303915

#TimeUsernameProblemLanguageResultExecution timeMemory
1303915I_FloPPed21Jail (JOI22_jail)C++20
0 / 100
5092 ms716 KiB
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N=120001;
struct arbore {
    long long scor,lz;
}aint[4*N];
int n,binlift[N][17],height[N],sub[N],top[N];
int get_lca(int a,int b) {

    if (height[a]<height[b])
        swap(a,b);

    for (int i=16;i>=0;i--) {

        if (height[binlift[a][i]]>=height[b])
            a=binlift[a][i];
    }

    if (a==b)
        return a;

    for (int i=16;i>=0;i--) {
        if (binlift[a][i]!=binlift[b][i]) {
            a=binlift[a][i];
            b=binlift[b][i];
        }
    }
    return binlift[a][0];
}
vector<int>adj[N];
void propaga(int nod) {

    if (aint[nod].lz==0)
        return;
    aint[nod*2].scor += aint[nod].lz;
    aint[nod*2+1].scor += aint[nod].lz;
    aint[nod*2].lz += aint[nod].lz;
    aint[nod*2+1].lz += aint[nod].lz;
    aint[nod].lz = 0;
}
void update(int nod,int st,int dr,int l,int r,int val) {
    if (l<=st && dr<=r) {
        aint[nod].scor+=val;
        aint[nod].lz+=val;
        return ;
    }
    else
        if (l>dr || st>r) {
            return;
        }

    propaga(nod);
    int mij = (st+dr)/2;
    update(nod*2, st, mij, l ,r, val);
    update(nod*2+1 ,mij+1, dr , l , r , val);

    aint[nod].scor=min(aint[nod*2].scor, aint[nod*2+1].scor);
}

int query(int nod, int st, int dr) {

    if (st==dr)
        return st;

    int mij=(st+dr)/2;
    if (aint[nod*2].scor==1)
        return query(nod*2,st,mij);
    else
        return query(nod*2+1,mij+1,dr);
}
void reset() {
    for (int i=1;i<=n;i++)
        adj[i].clear();
}
void dfs(int nod,int p) {

    height[nod]=height[p]+1;
    binlift[nod][0]=p;
    sub[nod]=1;
    for (int i=1;i<=16;i++) {
        binlift[nod][i]=binlift[binlift[nod][i-1]][i-1];
    }

    for (auto u:adj[nod]) {
        if (u!=p) {
            dfs(u,nod);
            sub[nod]+=sub[u];
        }
    }
}
int euler[N],where[N],global;
void dfs_hld(int nod,int p,int lant) {

    global++;
    euler[global]=nod;
    where[nod]=global;
    top[nod]=lant;
    int maxx=-1,go=-1;
    for (auto u:adj[nod]) {
        if (u!=p) {
            if (sub[u]>maxx) {
                maxx=sub[u];
                go=u;
            }
        }
    }

    if (go!=-1) {
        dfs_hld(go,nod,lant);
    }
    for (auto u:adj[nod]) {
        if (u!=p && u != go) {
            dfs_hld(u,nod,u);
        }
    }
}
int start[N];
void updateaza(int start,int end,int val) {

    while (height[start]>=height[end]) {
        int nod=top[start];
        if (height[top[start]]<height[end])
            nod=end;
        //cout<<start<<" "<<nod<<" "<<"huh"<<'\n';
        int interval=where[start];
        int interval_end=where[nod];

        //cout<<interval<<" "<<interval_end<<'\n';
        update(1,1,n,interval_end,interval,val);
        start=binlift[nod][0];
        //cout<<start<<" "<<nod<<'\n';
    }
}
void split(int a,int b,int scor) {

    int x=get_lca(a,b);
    //cout<<a<<" "<<b<<" "<<x<<'\n';
    updateaza(a,x,scor);
    //return;
    int t=b;
    for (int i=16;i>=0;i--) {
        if (height[binlift[t][i]]>height[x])
            t=binlift[t][i];
    }
    if (b!=x)
    updateaza(b,t,scor);
}
void solve() {

    cin>>n;
    for (int i=1;i<n;i++) {
        int x,y;
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(1,0);
    dfs_hld(1,0,1);
    for (int i=1;i<=n;i++) {
        update(1,1,n,i,i,1e9);
    }
    int m;
    cin>>m;
    for (int i=1;i<=m;i++) {
        int x,y;
        cin>>x>>y;
        start[x]=y;
        update(1,1,n,where[x],where[x],-1e9);
    }

    int cat_scade=m;
    for (int i=1;i<=n;i++) {
        if (start[i]) {

            int a=i;
            int b=start[i];;
            //cout<<a<<" "<<b<<'\n';
            split(a,b,1);
        }
    }
    //return ;
    //cout<<aint[1].scor<<'\n';
    int val=1;
    while (val==1) {

        val=aint[1].scor;
        //cout<<val<<" "<<"huh"<<endl;
        //cout<<val<<'\n';
        if (val==1) {
            int a=query(1,1,n);
            cat_scade--;
            update(1,1,n,a,a,1e9);
            int b=start[a];
            //cout<<a<<" "<<b<<'\n';
            split(a,b,-1);
            if (cat_scade==0)
                break;
        }
    }
    if (cat_scade==0) {
        cout<<"Yes"<<'\n';
    }
    else
        cout<<"No"<<'\n';

    for (int i=1;i<=n;i++) {
        start[i]=0;
        adj[i].clear();
        top[i]=0;
    }
    for (int i=1;i<=4*n;i++) {
        aint[i].lz=0;
        aint[i].scor=0;
    }
    global=0;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int test;
    cin>>test;
    while (test--)
        solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...