Submission #1187605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187605		browntoad	Jail (JOI22_jail)	C++20	100 / 100	1212 ms	389184 KiB

jail

#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n) 
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define endl '\n'
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

const ll maxn = 120005;
const ll mod = 1e9+7;
const ll inf = 1ll<<60;
const int mxpw = 18;
const ll totti = maxn + 2 * (mxpw+1) * maxn + 4 * maxn;

ll pw(ll a, ll p){
    ll rt = 1;
    while(p > 0){
        if (p & 1){
            rt *= a;
            rt %= mod;
        }
        a *= a;
        a %= mod;
        p >>= 1;
    }
    return rt;
}
ll inv(int a){
    return pw(a, mod-2);
}

int n1, n2;
vector<int> g[maxn], g2[totti];
vector<pii> qqs; 
vector<pii> euler(maxn);

vector<int> itselfS(maxn), itselfT(maxn); 
int cid = 0;

vector<int> in(totti), occ(totti), dep(maxn);

int up[maxn][mxpw];
int forS[maxn][mxpw], forT[maxn][mxpw];
bool ispar(int p, int u){
    return euler[p].f <= euler[u].f && euler[u].s <= euler[p].s;
}

int cval = 0;
int lca(int a, int b){
    if (dep[a] < dep[b]) swap(a, b);
    int tmp = dep[a] - dep[b];
    REP(i, mxpw){
        if ((1<<i)&tmp) a = up[a][i];
    }
    if (a == b) return a;
    RREP(i, mxpw){
        if (up[a][i] != up[b][i]){
            a = up[a][i];
            b = up[b][i];
        }
    }
    return up[a][0];
}
bool check(int a, int b, int tst){
    int lab = lca(a, b);
    //cout<<a<<' '<<b<<' '<<lab<<endl;
    if (!ispar(lab, tst)) return 0;
    return ispar(tst, a) || ispar(tst, b);
}

//int DEBUG = 0;

void add_edge(int u, int v){
    g2[u].pb(v);
    in[v]++;
    //DEBUG++;
    //cout<<u<<" - "<<v<<endl;
}
void dfs(int u, int pre){
    itselfS[u] = cid++;
    itselfT[u] = cid++;
    euler[u].f = cval++;
    up[u][0] = max(pre, 1);
    REP1(i, mxpw-1) up[u][i] = up[up[u][i-1]][i-1];
    REP(i, mxpw){
        if (i == 0){
            add_edge(itselfS[u], cid);
            add_edge(itselfS[up[u][0]], cid);
        }
        else{
            add_edge(forS[u][i-1], cid);
            add_edge(forS[up[u][i]][i-1], cid);
        }

        forS[u][i] = cid++; // actually, it includes 2^(0+1) nodes
    }
    REP(i, mxpw){
        if (i == 0){
            add_edge(cid, itselfT[u]);
            add_edge(cid, itselfT[up[u][0]]);
        }
        else{
            add_edge(cid, forT[u][i-1]);
            add_edge(cid, forT[up[u][i]][i-1]);
        }

        forT[u][i] = cid++; // actually, it includes 2^(0+1) nodes
    }


    for (auto v:g[u]){
        if (v == pre) continue;
        dep[v] = dep[u]+1;
        dfs(v, u);
    }
    euler[u].s = cval++;
}

vector<int> Sbwoah[maxn], Tbwoah[maxn];
vector<int> lrT(maxn), rlT(maxn), lrS(maxn), rlS(maxn); // query id -> big graph id
vector<int> headT(maxn), headS(maxn);

void init(){
    cin>>n1;
    REP1(i, n1) {
        g[i].clear();
        Sbwoah[i].clear();
        Tbwoah[i].clear();
        euler[i] = {-1, -1};
    }
    REP(i, n1-1){
        int u, v; cin>>u>>v;
        g[u].pb(v); g[v].pb(u);
    }
    cin>>n2;
    qqs.clear();
    REP(i, n2){
        int a, b; cin>>a>>b;
        Sbwoah[a].pb(i);
        Tbwoah[b].pb(i);
        qqs.pb({a, b});
    }
    REP1(i, n1) sort(ALL(Sbwoah[i]));
    REP1(i, n1) sort(ALL(Tbwoah[i]));
    cid = n2;
    cval = 1;

    int ctoti = 4*n2 + 2 * (mxpw+1) * n1 + n2 + 5;
    REP(i, ctoti){
        g2[i].clear();
        in[i] = 0;
        occ[i] = 0;
    }

}
void special(int u, int id){
    if (SZ(Sbwoah[u])){
        int pid = lower_bound(ALL(Sbwoah[u]), id)-Sbwoah[u].begin();
        if (pid >= SZ(Sbwoah[u]) || Sbwoah[u][pid] != id){
            add_edge(headS[u], id);
        }
        else{
            if (pid > 0) add_edge(lrS[Sbwoah[u][pid-1]], id);
            if (pid < SZ(Sbwoah[u])-1) add_edge(rlS[Sbwoah[u][pid+1]], id);
        }
    }
    if (SZ(Tbwoah[u])){
        int pid = lower_bound(ALL(Tbwoah[u]), id)-Tbwoah[u].begin();
        if (pid >= SZ(Tbwoah[u]) || Tbwoah[u][pid] != id){
            add_edge(id, headT[u]);
        }
        else{
            if (pid > 0) add_edge(id, rlT[Tbwoah[u][pid-1]]);
            if (pid < SZ(Tbwoah[u])-1) add_edge(id, lrT[Tbwoah[u][pid+1]]);
        }
    }
}
signed main(){
    IOS();
    int Q; cin>>Q;
    while(Q--){
        init();
        dfs(1, -1);

        /*REP(i, n2){
            REP(j, n2){
                if (i == j) continue;
                if (check(qqs[i].f, qqs[i].s, qqs[j].f)){
                    g2[j].pb(i);
                    //cout<<j<<'e'<<i<<endl;
                    in[i]++;
                }
                if (check(qqs[i].f, qqs[i].s, qqs[j].s)){
                    g2[i].pb(j);
                    in[j]++;
                    //cout<<i<<'e'<<j<<endl;
                }
            }
        }
        
        REP1(i, n1){
            cout<<itselfS[i]<<' ';
            REP(j, mxpw) cout<<forS[i][j]<<' ';
            cout<<endl;
        }
        cout<<endl;
        REP1(i, n1){
            cout<<itselfT[i]<<endl;
            REP(j, mxpw) cout<<forT[i][j]<<' ';
            cout<<endl;
        }
        cout<<endl;
        */
        
        REP1(i, n1){
            int plee = -1;
            REP(j, SZ(Sbwoah[i])){
                if (plee != -1) add_edge(plee, cid);
                add_edge(Sbwoah[i][j], cid);
                lrS[Sbwoah[i][j]] = cid;
                if (j == SZ(Sbwoah[i])-1) headS[i] = cid;
                plee = cid++;
            }
            plee = -1;
            RREP(j, SZ(Sbwoah[i])){
                if (plee != -1) add_edge(plee, cid);
                add_edge(Sbwoah[i][j], cid);
                rlS[Sbwoah[i][j]] = cid;
                plee = cid++;
            }

            plee = -1;
            REP(j, SZ(Tbwoah[i])){
                if (plee != -1) add_edge(plee, cid);
                else headT[i] = cid;
                add_edge(cid, Tbwoah[i][j]);
                lrT[Tbwoah[i][j]] = cid;
                plee = cid++;
            }
            plee = -1;
            RREP(j, SZ(Tbwoah[i])){
                if (plee != -1) add_edge(plee, cid);
                add_edge(cid, Tbwoah[i][j]);
                rlT[Tbwoah[i][j]] = cid;
                plee = cid++;
            }
        }
        
        REP(i, n2){
            add_edge(i, itselfS[qqs[i].f]);
            add_edge(itselfT[qqs[i].s], i);
        }
        

        //cout<<DEBUG<<endl;
        REP(i, n2){
            int lcc = lca(qqs[i].f, qqs[i].s);
            special(qqs[i].f, i);
            special(qqs[i].s, i);
            if (lcc == qqs[i].f){
                int cur = up[qqs[i].s][0], expdis = -dep[lcc] + dep[qqs[i].s] - 1;
                REP(b, mxpw){
                    if ((1<<b)&expdis){
                        if (b == 0) add_edge(itselfS[cur], i);
                        else add_edge(forS[cur][b-1], i);
                        if (b == 0) add_edge(i, itselfT[cur]);
                        else add_edge(i, forT[cur][b-1]);
                        cur = up[cur][b];
                    }
                }
            }
            else if (lcc == qqs[i].s){
                int cur = up[qqs[i].f][0], expdis = -dep[lcc] + dep[qqs[i].f] - 1;
                REP(b, mxpw){
                    if ((1<<b)&expdis){
                        if (b == 0) add_edge(itselfS[cur], i);
                        else add_edge(forS[cur][b-1], i);
                        if (b == 0) add_edge(i, itselfT[cur]);
                        else add_edge(i, forT[cur][b-1]);
                        cur = up[cur][b];
                    }
                }
            }
            else{
                int cur = up[qqs[i].f][0], expdis = -dep[lcc] + dep[qqs[i].f];
                REP(b, mxpw){
                    if ((1<<b)&expdis){
                        if (b == 0) add_edge(itselfS[cur], i);
                        else add_edge(forS[cur][b-1], i);
                        if (b == 0) add_edge(i, itselfT[cur]);
                        else add_edge(i, forT[cur][b-1]);
                        cur = up[cur][b];
                    }
                }
                cur = up[qqs[i].s][0]; expdis = -dep[lcc] + dep[qqs[i].s]-1;
                REP(b, mxpw){
                    if ((1<<b)&expdis){
                        if (b == 0) add_edge(itselfS[cur], i);
                        else add_edge(forS[cur][b-1], i);
                        if (b == 0) add_edge(i, itselfT[cur]);
                        else add_edge(i, forT[cur][b-1]);
                        cur = up[cur][b];
                    }
                }
            }
            
            
        }
        //cout<<DEBUG<<endl;

        queue<int> qu;
        REP(i, cid){
            if (in[i] == 0){
                qu.push(i);
            }
        }
        while(SZ(qu)){
            int tp = qu.front(); qu.pop();
            occ[tp] = 1;
            for (auto v:g2[tp]){
                in[v]--;
                if (in[v] == 0) qu.push(v);
            }
        }

        /*REP(i, cid){
            cout<<i<<'+'<<endl;
            for (auto y:g2[i]) cout<<y<<' ';
            cout<<endl;
        }
        */
        

        bool ex = 0;
        REP(i, cid) if (occ[i] == 0) {
            ex = 1;
            //cout<<'p'<<i<<endl;
        }
        
        cout<<(ex?"No":"Yes")<<endl;
    }

}
/*
5
6
1 2
2 3
3 4
4 5
5 6
1
5 1

6
1 2
2 3
3 4
4 5
5 6
3
1 3
2 4
3 6

4
1 2
2 3
3 4
2
1 3
4 2

8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4
1 3
2 4
7 5
8 6

6
1 2
2 3
3 4
4 5
5 6
3
1 4
2 3
5 6

1
7
1 2
2 3
3 4
4 5
5 6
6 7
1
7 1

*/

• 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