Submission #1186692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186692		browntoad	Jail (JOI22_jail)	C++20	61 / 100	5098 ms	74308 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 = 5e5+5;
const ll mod = 1e9+7;
const ll inf = 1ll<<60;

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[maxn];
vector<pii> qqs; 
vector<pii> euler(maxn);

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

const int mxpw = 18;
int up[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);
}
void dfs(int u, int pre){
    euler[u].f = cval++;
    up[u][0] = max(pre, 1ll);
    REP1(i, mxpw-1) up[u][i] = up[up[u][i-1]][i-1];
    for (auto v:g[u]){
        if (v == pre) continue;
        dep[v] = dep[u]+1;
        dfs(v, u);
    }
    euler[u].s = cval++;
}

void init(){
    cin>>n1;
    REP1(i, n1) {
        g[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;
    REP(i, n2) {
        g2[i].clear();
        in[i] = 0;
        occ[i] = 0;
    }
    qqs.clear();
    REP(i, n2){
        int a, b; cin>>a>>b;
        qqs.pb({a, b});
    }
    cval = 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;
                }
            }
        }
        queue<int> qu;
        REP(i, n2){
            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);
            }
        }
        bool ex = 0;
        REP(i, n2) if (occ[i] == 0) ex = 1;
        cout<<(ex?"No":"Yes")<<endl;
    }

}

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