Submission #1166041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166041		tw20000807	Jail (JOI22_jail)	C++20	61 / 100	5094 ms	43412 KiB

jail

#include<bits/stdc++.h>
#define int long long
#define all(v) v.begin(), v.end()
#define SZ(x) (int)x.size()
#define pii pair<int, int>
#define X first
#define Y second

using namespace std;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;//    998244353;
const int llmx = 1e18;
struct BIT{
	vector< int > tree;
	int n;
	BIT(int N){
		n = N;
		tree.resize(N + 2);
	}
	void modify(int id, int val){for(; id <= n; id += id&-id) tree[id] += val;}
	int query(int id){
		int re = 0;
		for(; id; id-=id&-id) re += tree[id];
		return re;
	}
	int query(int l, int r){return query(r) - query(l - 1);}
};
void sol(){
    int n; cin >> n;
    vector< vector< int > > g(n + 1);
    for(int i = 1; i < n; ++i){
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int m; cin >> m;
    vector< pii > v(m);
    for(auto &[a, b] : v) cin >> a >> b;
    vector< int > in(n + 1), out(n + 1), dep(n + 1);
    vector< vector< int > > anc(21, vector< int >(n + 1));
    
    int dfn = 1;
    auto dfs = [&](auto dfs, int cur, int par) -> void {
        in[cur] = dfn++;
        dep[cur] = dep[par] + 1;
        anc[0][cur] = par;
        for(int i = 1; i <= 20; ++i){
            anc[i][cur] = anc[i - 1][anc[i - 1][cur]];
        }
        for(auto &k : g[cur]) if(k != par) {
            dfs(dfs, k, cur);
        }
        out[cur] = dfn;
    };
    auto lca = [&](int a, int b) -> int {
        if(dep[a] < dep[b]) swap(a, b);
        for(int d = dep[a] - dep[b], p = 0; d; d >>= 1, ++p) if(d & 1){
            a = anc[p][a];
        }
        if(a == b) return a;
        for(int i = 20; i >= 0; --i) if(anc[i][a] != anc[i][b]){
            a = anc[i][a], b = anc[i][b];
        }
        assert(anc[0][a] == anc[0][b]);
        return anc[0][a];
    };
    dfs(dfs, 1, 1);
    auto chk_anc = [&](int a, int b) -> bool { // a is b anc ?
        return in[a] <= in[b] && in[b] < out[a];
    };
    auto chk = [&](int a, int b, int c) -> bool {
        int l = lca(a, b);
        // cerr << "chk : " << a << " " << b << " " << c << " : " << (chk_anc(l, c) && (chk_anc(c, a) || chk_anc(c, b))) << "\n";
        return (chk_anc(l, c) && (chk_anc(c, a) || chk_anc(c, b)));
    };
    // BIT bit(n + 2);
    vector< int > ord;
    {
        vector< vector< int > > ng(m);
        vector< int > deg(m);
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < m; ++j) if(i != j) {
                if(chk(v[i].X, v[i].Y, v[j].X)){
                    ng[j].push_back(i);
                    deg[i]++;
                }
                if(chk(v[i].X, v[i].Y, v[j].Y)){
                    ng[i].push_back(j);
                    deg[j]++;
                }
            }
        }
        int id = 0;
        for(int i = 0; i < m; ++i) if(deg[i] == 0) ord.push_back(i);
        while(id < SZ(ord)){
            int cur = ord[id++];
            // cerr << cur << " ";
            for(auto &k : ng[cur]) if(--deg[k] == 0){
                ord.push_back(k);
            }
        }
        // cerr << "--\n";
        for(int i = 0; i < m; ++i) if(deg[i]){
            cout << "No\n";
            return;
        }
        cout << "Yes\n";
    }
    // for(int i = 0; i < m; ++i){
    //     auto &[a, b] = v[i];
    //     bit.modify(in[a], 1);
    //     bit.modify(out[b], -1);
    // }
    // for(int i = 0; i < m; ++i){
    //     int go = -1;
    //     for(int i = 1; i <= m; ++i){
    //         if()
    //     }
    //     cout << "No\n";
    // }
    // cout << "Yes\n";
}
/*


*/
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cerr.tie(0);
    int t = 1; cin >> t;
    while(t--) sol();
}

• 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