Submission #993814

#	Time	Username	Problem	Language	Result	Execution time	Memory
993814		snpmrnhlol	Jail (JOI22_jail)	C++17	100 / 100	744 ms	86548 KiB

jail

#include<bits/stdc++.h>
using namespace std;
const int N = 12e4;
const int S = 5*N;
const int logN = 20;
int t;
vector <int> e[N];
vector <int> e2[S];
int deg[S];
int n,m;
int ls[S],rs[S];
queue <int> q;
int cnt = 0;
int root1;
int root2;
int sub[N];
int dpth[N];
int cnt2 = 0;
int st[N],st2[N];
int starts[N],endz[N];
int top[N];
int p1[N],p2[N];
int su[N],sw[N];
int pr[N];
int rmq[N][logN];
void build1(int l = 0,int r = n - 1,int node = 0){
    if(l != r){
        int mij = (l + r)/2;
        if(l != mij)ls[node] = cnt++;
        else ls[node] = p1[mij];
        if(mij + 1 != r)rs[node] = cnt++;
        else rs[node] = p1[mij + 1];
        //cout<<"addedge:"<<node<<' '<<ls[node]<<'\n';
        //cout<<"addedge:"<<node<<' '<<rs[node]<<'\n';
        e2[node].push_back(ls[node]);
        e2[node].push_back(rs[node]);
        build1(l,mij,ls[node]);
        build1(mij + 1,r,rs[node]);
    }
}
void build2(int l = 0,int r = n - 1,int node = 0){
    if(l != r){
        int mij = (l + r)/2;
        if(l != mij)ls[node] = cnt++;
        else ls[node] = p2[mij];
        if(mij + 1 != r)rs[node] = cnt++;
        else rs[node] = p2[mij + 1];
        //cout<<"addedge:"<<ls[node]<<' '<<node<<'\n';
        //cout<<"addedge:"<<rs[node]<<' '<<node<<'\n';
        e2[ls[node]].push_back(node);
        e2[rs[node]].push_back(node);
        build2(l,mij,ls[node]);
        build2(mij + 1,r,rs[node]);
    }
}
void dfs(int node, int p){
    pr[node] = p;
    sub[node] = 1;
    if(p == -1)dpth[node] = 0;
    else dpth[node] = dpth[p] + 1;
    for(auto i:e[node]){
        if(i == p)continue;
        dfs(i, node);
        sub[node]+=sub[i];
    }
    int mxid = -1;
    for(int i = 0;i < e[node].size();i++){
        if(e[node][i] == p)continue;
        if(mxid == -1 || sub[e[node][mxid]] < sub[e[node][i]]){
            mxid = i;
        }
    }
    if(mxid != -1){
        swap(e[node][mxid],e[node][0]);
    }
    for(int i = 0;i < e[node].size();i++){
        if(e[node][i] == p){
            swap(e[node][i],e[node].back());
            e[node].pop_back();
            break;
        }
    }
}
int last[N],first[N];
int laen[N],firen[N];
int rp1[N],rp2[N];
int cnt3 = 0,cnt4 = 0;
void dfs2(int node, int p){
    //cout<<"dfs:"<<node<<' '<<p<<'\n';
    st[node] = cnt2++;
    st2[cnt2 - 1] = node;
    bool ok = 0;
    if(starts[node] != -1){
        //cout<<"assignment:"<<node<<'\n';
        rp1[node] = cnt3++;
        p1[cnt3 - 1] = starts[node];
    }
    if(endz[node] != -1){
        rp2[node] = cnt4++;
        p2[cnt4 - 1] = endz[node];
    }
    if(starts[node] != -1){
        first[node] = node;
    }else if(top[node] == node){
        first[node] = -1;
    }else{
        first[node] = first[p];
    }
    //cout<<node<<' '<<first[node]<<'\n';
    if(endz[node] != -1){
        firen[node] = node;
    }else if(top[node] == node){
        firen[node] = -1;
    }else{
        firen[node] = firen[p];
    }
    for(auto i:e[node]){
        if(i == p)continue;
        if(!ok){
            top[i] = top[node];
        }else{
            top[i] = i;
        }
        dfs2(i, node);
        ok = 1;
    }
    if(starts[node] != -1){
        last[node] = node;
    }else if(!e[node].empty()){
        last[node] = last[e[node][0]];
    }else{
        last[node] = -1;
    }
    if(endz[node] != -1){
        laen[node] = node;
    }else if(!e[node].empty()){
        laen[node] = laen[e[node][0]];
    }else{
        laen[node] = -1;
    }
}
void updstart(int ql,int qr,int id,int l = 0,int r = m - 1,int node = root1){
    assert(ql <= qr);
    if(ql <= l && r <= qr){
        e2[id].push_back(node);
        //cout<<"addedge:"<<id<<' '<<node<<'\n';
    }else{
        int mij = (l + r)/2;
        if(qr <= mij){
            updstart(ql,qr,id,l,mij,ls[node]);
        }else if(mij + 1 <= ql){
            updstart(ql,qr,id,mij + 1,r,rs[node]);
        }else{
            updstart(ql,qr,id,l,mij,ls[node]);
            updstart(ql,qr,id,mij + 1,r,rs[node]);
        }
    }
}
void updends(int ql,int qr,int id,int l = 0,int r = m - 1,int node = root2){
    assert(ql <= qr);
    if(ql <= l && r <= qr){
        e2[node].push_back(id);
        //cout<<"addedge:"<<node<<' '<<id<<'\n';
    }else{
        int mij = (l + r)/2;
        if(qr <= mij){
            updends(ql,qr,id,l,mij,ls[node]);
        }else if(mij + 1 <= ql){
            updends(ql,qr,id,mij + 1,r,rs[node]);
        }else{
            updends(ql,qr,id,l,mij,ls[node]);
            updends(ql,qr,id,mij + 1,r,rs[node]);
        }
    }
}
int prog(int u,int w){
    int df = dpth[w] - dpth[u] - 1;
    if(df < 0)return pr[u];
    for(int i = logN - 1;i >= 0;i--){
        if(df>>i&1){
            df-=(1<<i);
            w = rmq[w][i];
        }
    }
    if(pr[w] == u)return w;
    return pr[u];
}
void addstarts(int u,int w,int id){
    u = prog(u,w);
    while(top[u] != top[w]){
        if(dpth[top[u]] > dpth[top[w]])swap(u,w);
        //cout<<"fire:"<<u<<' '<<w<<' '<<id<<' '<<first[w]<<' '<<last[top[w]]<<' '<<rp1[first[w]]<<' '<<rp1[last[top[w]]]<<'\n';
        if(first[w] != -1 && last[top[w]] != -1 && rp1[last[top[w]]] <= rp1[first[w]]){
            //cout<<first[w]<<' '<<last[top[w]]<<' '<<id<<'\n';
            updstart(rp1[last[top[w]]],rp1[first[w]],id);
        }
        w = pr[top[w]];
    }
    if(dpth[u] > dpth[w])swap(u,w);
    if(first[w] != -1 && last[u] != -1 && rp1[last[u]] <= rp1[first[w]]){
        //cout<<last[u]<<' '<<first[w]<<' '<<id<<'\n';
        updstart(rp1[last[u]],rp1[first[w]],id);
    }
}
void addends(int u,int w,int id){
    w = prog(w,u);
    while(top[u] != top[w]){
        if(dpth[top[u]] > dpth[top[w]])swap(u,w);
        if(firen[w] != -1 && laen[top[w]] != -1 && rp2[laen[top[w]]] <= rp2[firen[w]]){
            //cout<<firen[w]<<' '<<laen[top[w]]<<' '<<id<<"end\n";
            updends(rp2[laen[top[w]]],rp2[firen[w]],id);
        }
        w = pr[top[w]];
    }
    if(dpth[u] > dpth[w])swap(u,w);
    if(firen[w] != -1 && laen[u] != -1 && rp2[laen[u]] <= rp2[firen[w]]){
        //cout<<laen[u]<<' '<<firen[w]<<' '<<id<<"end\n";
        updends(rp2[laen[u]],rp2[firen[w]],id);
    }
}
bool topsort(){
    int nr = 0;
    for(int i = 0;i < cnt;i++){
        deg[i] = 0;
    }
    for(int i = 0;i < cnt;i++){
        for(auto j:e2[i]){
            deg[j]++;
        }
    }
    for(int i = 0;i < cnt;i++){
        if(deg[i] == 0)q.push(i);
    }
    while(!q.empty()){
        int x = q.front();
        nr++;
        q.pop();
        for(auto i:e2[x]){
            deg[i]--;
            if(deg[i] == 0){
                q.push(i);
            }
        }
    }
    return nr == cnt;
}
void solve(){
    cnt3 = cnt4 = 0;
    cin>>n;
    for(int i = 0;i < n - 1;i++){
        int u,w;
        cin>>u>>w;
        u--;w--;
        e[w].push_back(u);
        e[u].push_back(w);
    }
    for(int i = 0;i < n;i++){
        starts[i] = -1;
        endz[i] = -1;
    }
    cin>>m;
    for(int i = 0;i < m;i++){
        int u,w;
        cin>>u>>w;
        u--;w--;
        starts[u] = i;
        endz[w] = i;
        su[i] = u;
        sw[i] = w;
    }
    cnt2 = 0;
    top[0] = 0;
    dfs(0, -1);
    dfs2(0, -1);
    cnt = m;
    root1 = cnt++;
    build1(0,m - 1,cnt - 1);
    root2 = cnt++;
    build2(0,m - 1,cnt - 1);
    /*for(int i = 0;i < n;i++){
        for(auto j:e2[i]){
            cout<<"edge:"<<i<<' '<<j<<'\n';
        }
    }*/
    for(int i = 0;i < n;i++){
        rmq[i][0] = pr[i];
        //cout<<first[i]<<' '<<last[i]<<' '<<i<<' '<<top[i]<<'\n';
    }
    for(int j = 1;j < logN;j++){
        for(int i = 0;i < n;i++){
            rmq[i][j] = rmq[rmq[i][j - 1]][j - 1];
        }
    }
    for(int i = 0;i < m;i++){
        int u = su[i];
        int w = sw[i];
        addstarts(u,w,i);
        addends(u,w,i);
    }
    bool ok = topsort();
    if(ok){
        cout<<"Yes\n";
    }else{
        cout<<"No\n";
    }
    for(int i = 0;i < n;i++){
        e[i].clear();
    }
    for(int i = 0;i < cnt;i++){
        e2[i].clear();
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
/**
1
12
1 2
1 3
3 4
4 5
5 6
7 8
7 9
9 10
10 11
11 12
1 7
6
1 8
2 11
3 12
4 9
5 10
6 7
**/

Compilation message (stderr)

jail.cpp: In function 'void dfs(int, int)':
jail.cpp:67:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i = 0;i < e[node].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~
jail.cpp:76:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i = 0;i < e[node].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23