제출 #706542

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
706542		becaido	Jail (JOI22_jail)	C++17	0 / 100	17 ms	11648 KiB

jail

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int INF = 1e9;
const int SIZE = 24e4 + 5;
const int H = __lg(SIZE) + 1;

int n, m;
bool ans;
vector<int> adj[SIZE];
int s[SIZE], t[SIZE], c[SIZE];
int h[SIZE], to[SIZE][H + 1];

vector<int> g[SIZE];
int deg[SIZE];
queue<int> q;

void dfs(int pos, int fa) {
    for (int np : adj[pos]) if (np != fa) {
        h[np] = h[pos] + 1;
        to[np][0] = pos;
        dfs(np, pos);
    }
}

int jump(int pos, int k) {
    if (k < 0) return 0;
    int cnt = 0;
    while (k) {
        if (k & 1) pos = to[pos][cnt];
        cnt++;
        k >>= 1;
    }
    return pos;
}

int lca(int a, int b) {
    if (h[a] < h[b]) swap(a, b);
    a = jump(a, h[a] - h[b]);
    if (a == b) return a;
    for (int i = H; i >= 0; i--) if (to[a][i] != to[b][i]) {
        a = to[a][i];
        b = to[b][i];
    }
    return to[a][0];
}

bool on_path(int pos, int a, int c, int b) {
    return h[pos] >= h[c] && (jump(a, h[a] - h[pos]) == pos || jump(b, h[b] - h[pos]) == pos);
}

void add_edge(int a, int b) {
    g[a].pb(b);
    deg[b]++;
}

void add(int a, int b) {
    vector<int> v;
    for (int x : {s[a], s[b]}) for (int y : {t[a], t[b]}) {
        int z = lca(x, y);
        if (on_path(z, s[a], c[a], t[a]) && on_path(z, s[b], c[b], t[b])) v.pb(z);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    if (v.size() == 0) return;
    if (v.size() == 1) {
        int k = v[0];
        if (s[a] == k) add_edge(a, b);
        else if (s[b] == k) add_edge(b, a);
        else if (t[a] == k) add_edge(b, a);
        else if (t[b] == k) add_edge(a, b);
        return;
    }
    if (v.size() == 3) {
        int mn = h[v[0]];
        for (int x : v) mn = min(mn, h[x]);
        for (int i = 0; i < 3; i++) if (h[v[i]] == mn) {v.erase(v.begin() + i); break;}
    }

    assert(v.size() == 2);
    int k1 = v[0], k2 = v[1];
    bool isa, ita, isb, itb;
    isa = s[a] == k1 || s[a] == k2;
    ita = t[a] == k1 || t[a] == k2;
    isb = s[b] == k1 || s[b] == k2;
    itb = t[b] == k1 || t[b] == k2;

    if ((isa && ita) || (isb && itb)) {
        ans = 0;
        return;
    }

    if ((isa && isb) || (ita && itb)) {
        ans = 0;
        return;
    }

    if (isa) add_edge(a, b);
    else if (isb) add_edge(b, a);
    else if (ita) add_edge(b, a);
    else if (itb) add_edge(a, b);
}

void solve() {
    cin >> n;
    FOR (i, 1, n) adj[i].clear();
    FOR (i, 2, n) {
        int a, b;
        cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    h[1] = 1, dfs(1, 1);
    FOR (j, 1, H) FOR (i, 1, n) to[i][j] = to[to[i][j - 1]][j - 1];

    cin >> m;
    FOR (i, 1, m) {
        cin >> s[i] >> t[i];
        c[i] = lca(s[i], t[i]);
        g[i].clear();
        deg[i] = 0;
    }
    ans = 1;
    FOR (i, 1, m) FOR (j, i + 1, m) {
        add(i, j);
        if (!ans) {
            cout << "No\n";
            return;
        }
    }
    FOR (i, 1, m) if (!deg[i]) q.push(i);
    int cnt = 0;
    while (q.size()) {
        int pos = q.front();
        q.pop();
        cnt++;
        for (int np : g[pos]) if (--deg[np] == 0) q.push(np);
    }
    cout << (cnt == m ? "Yes" : "No") << '\n';
}

int main() {
    Waimai;
    int tt;
    cin >> tt;
    while (tt--) solve();
}

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