Submission #1264439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264439		M_W_13	Jail (JOI22_jail)	C++20	0 / 100	3 ms	6472 KiB

jail

#include <bits/stdc++.h>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
#define pb push_back
#define st first
#define nd second
const int MAXN = 1 << 17;
vector<int> graf[MAXN];
vector<int> przez[MAXN];
int konczy[MAXN];
bool czy[MAXN];
int ilekon[MAXN];
int ilena[MAXN];
int ojc[MAXN];
int depth[MAXN];
pair<int, int> pyt[MAXN];
queue<int> jakie;

void dfs(int v, int last) {
    // cout << "v = " << v << endl;
    depth[v] = depth[last] + 1;
    ojc[v] = last;
    for (auto syn: graf[v]) {
        if (syn == last) continue;
        dfs(syn, v);
    }
}

void odj(int v) {
    if (konczy[v] != 0) {
        int j = konczy[v];
        ilekon[j]--;
        if (ilena[j] == 0 && ilekon[j] == 0) {
            jakie.push(j);
        }
    }
}

void usun(int i) {
    int a = pyt[i].st;
    int b = pyt[i].nd;
    for (auto j: przez[a]) {
        ilena[j]--;
        if (ilena[j] == 0 && ilekon[j] == 0) {
            jakie.push(j);
        }
    }
    if (depth[a] > depth[b]) {
        swap(a, b);
    }
    while (depth[b] > depth[a]) {
        odj(b);
        b = ojc[b];
    }
    while (a != b) {
        odj(a);
        odj(b);
        a = ojc[a];
        b = ojc[b];
    }
    odj(a);
}

void dod(int i) {
    int a = pyt[i].st;
    int b = pyt[i].nd;
    if (depth[a] > depth[b]) {
        swap(a, b);
    }
    while (depth[b] > depth[a]) {
        if (czy[b]) {
            ilena[i]++;
        }
        przez[b].pb(i);
        b = ojc[b];
    }
    while (a != b) {
        if (czy[a]) {
            ilena[i]++;
        }
        if (czy[b]) {
            ilena[i]++;
        }
        przez[a].pb(i);
        przez[b].pb(i);
        a = ojc[a];
        b = ojc[b];
    }
    przez[a].pb(i);
    if (czy[a]) {
        ilena[i]++;
    }
}

void solve() {
    int n;
    cin >> n;
    rep(i, n - 1) {
        int a, b;
        cin >> a >> b;
        graf[a].pb(b);
        graf[b].pb(a);
    }
    depth[1] = 0;
    dfs(1, 1);
    int m;
    cin >> m;
    rep(i, m) {
        ilena[i + 1] = -1;
        ilekon[i + 1] = -1;
    }
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        pyt[i + 1] = {a, b};
        czy[a] = true;
    }
    rep(i, m) {
        dod(i + 1);
    }
    rep(i, m) {
        int b = pyt[i + 1].nd;
        int sz = przez[b].size();
        ilekon[i + 1] += sz;
    }
    rep(i, m) {
        // cout << "ilena = " << ilena[i + 1] << " ilekon = " << ilekon[i + 1] << '\n';
        if (ilena[i + 1] == 0 && ilekon[i + 1] == 0) {
            jakie.push(i + 1);
        }
    }
    int s = 0;
    while (!jakie.empty()) {
        int i = jakie.front();
        jakie.pop();
        // cout << "i = " << i << '\n';
        s++;
        usun(i);
    }
    rep(i, n + 1) {
        czy[i] = false;
        graf[i].clear();
        przez[i].clear();
        konczy[i] = 0;
    }
    if (s == m) {
        cout << "Yes" << '\n';
        return ;
    }
    cout << "No" << '\n';
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
	cin >> t;
	while(t--) {
		solve();
	}
	return 0;
}

• 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