Submission #994219

#	Time	Username	Problem	Language	Result	Execution time	Memory
994219		vjudge1	Jail (JOI22_jail)	C++14	72 / 100	4096 ms	1048576 KiB

jail

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 120'000;
const int logn = 17;

int n, m;
vector<int> graph[1 + maxn];
int lift[1 + maxn][logn];
int dep[1 + maxn];
vector<int> dag[1 + maxn];
bool vis_dag[1 + maxn];
vector<int> top;
int pos[1 + maxn];
int in[1 + maxn];
int out[1 + maxn];
int timer;
int by_start[1 + maxn];
int by_end[1 + maxn];

void dfs_lift(int cur) {
    timer++;
    in[cur] = timer;
    for(int nei : graph[cur]) {
        if(nei != lift[cur][0]) {
            lift[nei][0] = cur;
            dep[nei] = dep[cur] + 1;
            dfs_lift(nei);
        }
    }
    timer++;
    out[cur] = timer;
}

int lca(int a, int b) {
    if(dep[a] > dep[b]) {
        swap(a, b);
    }
    for(int j = logn - 1; j >= 0; j--) {
        if(dep[b] - (1 << j) >= dep[a]) {
            b = lift[b][j];
        }
    }
    if(a == b) {
        return a;
    }
    for(int j = logn - 1; j >= 0; j--) {
        if(lift[a][j] != lift[b][j]) {
            a = lift[a][j];
            b = lift[b][j];
        }
    }
    return lift[b][0];
}

void add_edge(int a, int b) {
    dag[a].pb(b);
}

void dfs_top(int cur) {
    vis_dag[cur] = true;
    for(int nei : dag[cur]) {
        if(!vis_dag[nei]) {
            dfs_top(nei);
        }
    }
    top.pb(cur);
}

#define ancestor(a, b) (in[a] <= in[b] && out[a] >= out[b])

bool on_path(int a, int b, int c) {
    int ab = lca(a, b);
    return ancestor(ab, c) && (ancestor(c, a) || ancestor(c, b));
}

void add(int other_idx, int node) {
    if(by_start[node] != 0 && by_start[node] != other_idx) {
        add_edge(by_start[node], other_idx);
    }
    if(by_end[node] != 0 && by_end[node] != other_idx) {
        add_edge(other_idx, by_end[node]);
    }
}

bool solve() {
    cin >> n;
    for(int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].pb(b);
        graph[b].pb(a);
    }
    dfs_lift(1);
    lift[1][0] = 1;
    for(int j = 1; j < logn; j++) {
        for(int i = 1; i <= n; i++) {
            lift[i][j] = lift[lift[i][j - 1]][j - 1];
        }
    }
    cin >> m;
    vector<pii > pairs;
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        pairs.pb(mp(a, b));
        by_start[a] = i;
        by_end[b] = i;
    }
    for(int i = 0; i < m; i++) {
        int a = pairs[i].fi, b = pairs[i].se;
        int ab = lca(a, b);
        while(a != ab) {
            add(i + 1, a);
            a = lift[a][0];
        }
        while(b != ab) {
            add(i + 1, b);
            b = lift[b][0];
        }
        add(i + 1, ab);
    }
    for(int i = 1; i <= m; i++) {
        if(!vis_dag[i]) {
            dfs_top(i);
        }
    }
    reverse(top.begin(), top.end());
    int idx = 0;
    for(int x : top) {
        idx++;
        pos[x] = idx;
    }
    for(int a = 1; a <= m; a++) {
        for(int b : dag[a]) {
            if(pos[b] < pos[a]) {
                return false;
            }
        }
    }
    return true;
}

/*
int n, m;
vector<int> graph[1 + maxn];
int lift[1 + maxn][logn];
int dep[1 + maxn];
vector<int> dag[1 + maxn];
bool vis_dag[1 + maxn];
vector<int> top;
int pos[1 + maxn];
int in[1 + maxn];
int out[1 + maxn];
int timer;
int by_start[1 + maxn];
int by_end[1 + maxn];
*/

void reset() {
    for(int i = 1; i <= max(n, m); i++) {
        graph[i].clear();
        for(int j = 0; j < logn; j++) {
            lift[i][j] = 0;
        }
        dep[i] = 0;
        dag[i].clear();
        vis_dag[i] = false;
        pos[i] = 0;
        in[i] = 0;
        out[i] = 0;
        by_start[i] = 0;
        by_end[i] = 0;
    }
    top.clear();
    timer = 0;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while(T--) {
        cout << (solve() ? "Yes" : "No") << "\n";
        reset();
    }
}

• 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