Submission #986522

#	Time	Username	Problem	Language	Result	Execution time	Memory
986522		ShaShi	Jail (JOI22_jail)	C++17	72 / 100	2659 ms	1048576 KiB

jail

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define kill(x) cout << x << endl, exit(0);
#define endl "\n"

 
using namespace std;
typedef long long ll;
typedef long double ld;
 

const int MAXN = (int)1e6 + 7;
const int MOD = 998244853;
const ll INF = (ll)1e18 + 7;


int t, n, m, q, tmp, tmp2, tmp3, tmp4, ans, k, u, v, w, flag, N, M;
int arr[MAXN], h[MAXN], st[MAXN], fn[MAXN], ind[MAXN], par[MAXN];
bool seen[MAXN];
vector<int> adj[MAXN], G[MAXN], ord, Ss[MAXN], T[MAXN];
vector<pii> edge;


void DFSsz(int v) {
    seen[v] = 1;

    for (int u:adj[v]) {
        if (seen[u]) continue;
        
        h[u] = h[v]+1; par[u] = v;

        DFSsz(u);
    }
}


inline void add_edge(int u, int v) {
    if (u == v) return;

    G[u].pb(v);
    edge.pb(mp(u, v));
}


inline void check(int ind, int v) {
    for (int x:Ss[v]) add_edge(x, ind);
    for (int x:T[v]) add_edge(ind, x);
}


inline void process(int ind, int u, int v) {
    if (h[u] > h[v]) swap(u, v);

    while (h[v] > h[u]) {
        check(ind, v); v = par[v];
    }

    while (u != v) {
        check(ind, u); check(ind, v);
        u = par[u]; v = par[v];
    }

    check(ind, u);
}


void DFS(int v) {
    seen[v] = 1;

    for (int u:G[v]) if (!seen[u]) DFS(u);
    
    ord.pb(v);
}


void solve() {
    cin >> n;

    for (int i=0; i<n+7; i++) adj[i].clear(), G[i].clear(), Ss[i].clear(), T[i].clear();
    edge.clear(); ord.clear(); fill(seen, seen+n+7, 0);
    fill(h, h+n+7, 0); fill(ind, ind+n+7, 0); fill(par, par+n+7, 0);

    for (int i=1; i<n; i++) {
        cin >> u >> v;

        adj[u].pb(v); adj[v].pb(u);
    }
    
    DFSsz(1);

    cin >> m;

    for (int i=1; i<=m; i++) {
        cin >> st[i] >> fn[i];

        Ss[st[i]].pb(i); T[fn[i]].pb(i);
    }

    for (int i=1; i<=m; i++) process(i, st[i], fn[i]);

    ord.clear(); fill(seen, seen+n+1, 0);

    for (int i=1; i<=m; i++) if (!seen[i]) DFS(i);
    for (int i=0; i<m; i++) ind[ord[i]] = i;

    for (auto cur:edge) {
        if (ind[cur.F] < ind[cur.S]) {
            cout << "No\n";
            return;
        }
    }

    cout << "Yes\n";
}


int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> t;

    while (t--) solve();

    return 0;
}

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