Submission #966765

#	Time	Username	Problem	Language	Result	Execution time	Memory
966765		LOLOLO	Jail (JOI22_jail)	C++17	49 / 100	5064 ms	318452 KiB

jail

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define           f    first
#define           s    second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 1.25e5;
vector <int> ed[N], ed2[N * 40];
int in[N], ou[N], dfstimer = 1, p[N][20], vi[N][20], vo[N][20], dep[N], st[N], en[N], cnt = 0;
char used[N * 40];

bool check_cycle(int u) {
    if (used[u] == 1)
        return 0;

    used[u] = 1; 
    for (auto x : ed2[u]) {
        if (used[x] != 2 && !check_cycle(x))
            return 0;
    }

    used[u] = 2;
    return 1;
}

void dfs(int u, int v) {
    vi[u][0] = ++cnt;
    vo[u][0] = ++cnt;
    if (st[u]) {
        ed2[st[u]].pb(vo[u][0]);
    }

    if (en[u]) {
        ed2[vi[u][0]].pb(en[u]);
    }

    dep[u] = dep[v] + 1;
    p[u][0] = v;

    for (int i = 1; i < 20; i++) {
        p[u][i] = p[p[u][i - 1]][i - 1];
        vi[u][i] = ++cnt;
        vo[u][i] = ++cnt;
        ed2[vo[u][i - 1]].pb(vo[u][i]);
        ed2[vo[p[u][i - 1]][i - 1]].pb(vo[u][i]);
        ed2[vi[u][i]].pb(vi[u][i - 1]);
        ed2[vi[u][i]].pb(vi[p[u][i - 1]][i - 1]);
    }

    ++dfstimer;
    in[u] = dfstimer;
    for (auto x : ed[u]) {
        if (x == v)
            continue;

        dfs(x, u);
    }

    ou[u] = dfstimer;
}

bool is(int a, int b) {
    return in[a] <= in[b] && ou[a] >= in[b]; 
}

int lca(int a, int b) {
    if (is(a, b))
        return a;

    if (is(b, a))
        return b;

    for (int i = 19; i >= 0; i--)
        if (is(p[a][i], b) == 0)
            a = p[a][i];

    return p[a][0];
}

int dis(int a, int b) {
    int c = lca(a, b);
    return dep[a] + dep[b] - dep[c] * 2;
}

void addedge(int a, int b, int id) {
    int k = dep[a] - dep[b] + 1;
    for (int j = 0; j < 20; j++) {
        if (k & (1 << j)) {
            ed2[id].pb(vi[a][j]);
            ed2[vo[a][j]].pb(id);
            a = p[a][j];
        }
    }
}

int find(int a, int k) {
    for (int j = 0; j < 20; j++)
        if (k & (1 << j))
            a = p[a][j];

    return a;
}

string solve() {
    int n;
    cin >> n;

    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        ed[a].pb(b);
        ed[b].pb(a);
    }

    int m;
    cin >> m;

    vector <pair <int, int>> save;

    for (int i = 1; i <= m; i++) {
        int s, t;
        cin >> s >> t;
        save.pb({s, t});
        st[s] = i, en[t] = i;
    }

    cnt = m;
    dfs(1, 1);

    int id = 0;
    for (auto x : save) {
        id++;
        int s = x.f, t = x.s;

        int a = s, b = t;
        if (dep[s] > dep[t])
            swap(s, t);

        //int c = lca(s, t);
        /*if (s == c) {
            addedge(p[t][0], find(t, dep[t] - dep[s] - 1), id);
        } else {
            addedge(p[s][0], c, id);
            addedge(p[t][0], c, id);
        }*/

        for (int i = 1; i <= n; i++) {
            if (i == a || i == b)
                continue;        

            if (dis(i, a) + dis(i, b) == dis(a, b)) {
                if (st[i]) {
                    ed2[st[i]].pb(id);
                }

                if (en[i]) {
                    ed2[id].pb(en[i]);
                }
            } 
        }

        if (en[a]) {
            ed2[id].pb(en[a]);
        }

        if (st[b]) {
            ed2[st[b]].pb(id);
        }
    }

    int is = 0;
    for (int i = 1; i <= m; i++) {
        if (used[i] == 0 && check_cycle(i) == 0) {
            is = 1;
            break;
        }
    }

    for (int i = 1; i <= n; i++) {
        ed[i].clear();
        st[i] = en[i] = dep[i] = 0;
    }

    for (int i = 1; i <= cnt; i++) {
        ed2[i].clear();
        used[i] = 0;
    }

    if (is == 0)
        return "Yes";

    return "No";
}

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);

    int t = 1;
    cin >> t;

    while (t--) {
        //solve();
        cout << solve() << "\n";
    }

    return 0;
}

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