Submission #1000431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000431		onbert	Jail (JOI22_jail)	C++17	0 / 100	5048 ms	94196 KiB

jail

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

void add(vector<pair<int,int>> &v, pair<int,int> x) {
    if (v.size() > 0 && x.second+1 == v.back().first) v.back().first = x.first;
    else v.push_back(x);
}

const int maxn = 120005, maxN = 480005, lgn = 17, INF = 1e18;
int n, m;
vector<int> ADJ[maxn], adj[maxn];
pair<int,int> a[maxn];
int sz[maxn], fa[maxn], d[maxn], newid[maxn], lim[maxn], cnter = 0;

void dfs1(int u) {
    sz[u] = 1;
    int f = -1;
    for (int v:ADJ[u]) {
        if (sz[v]) {
            f = v;
            continue;
        }
        dfs1(v);
        sz[u] += sz[v];
    }
    if (f!=-1) ADJ[u].erase(find(ADJ[u].begin(), ADJ[u].end(), f));
    // cout << u << endl;
    // for (int v:ADJ[u]) cout << v << " "; cout << endl;
    for (int j=1;j<ADJ[u].size();j++) if (sz[ADJ[u][j]] > sz[ADJ[u][0]]) swap(ADJ[u][0], ADJ[u][j]);
}
void dfs2(int u) {
    cnter++;
    newid[u] = cnter;
    for (int v:ADJ[u]) {
        d[cnter+1] = d[newid[u]] + 1;
        dfs2(v);
        fa[newid[v]] = newid[u];
    }
    lim[newid[u]] = cnter;
}
pair<int, vector<pair<int,int>>> binlift[maxn][lgn];
void dfs3(int u) {
    for (int i=1;i<lgn;i++) {
        if (binlift[u][i-1].first==-1 || binlift[binlift[u][i-1].first][i-1].first==-1) break;
        binlift[u][i].first = binlift[binlift[u][i-1].first][i-1].first;
        binlift[u][i].second = binlift[u][i-1].second;
        for (auto [L, R]:binlift[binlift[u][i-1].first][i-1].second) add(binlift[u][i].second, {L, R});
    }
    for (int v:adj[u]) {
        binlift[v][0] = {u, {{u, u}}};
        dfs3(v);
    }
}
vector<pair<int,int>> PATH(int u, int v) {
    if (d[u] > d[v]) swap(u, v);
    vector<pair<int,int>> U = {{u, u}}, V = {{v, v}};
    for (int i=lgn-1;i>=0;i--) if (d[v] - (1<<i) >= d[u]) {
        for (auto [L, R]:binlift[v][i].second) add(V, {L, R});
        v = binlift[v][i].first;
    }
    if (u==v) return V;
    for (int i=lgn-1;i>=0;i--) if (binlift[u][i].first != binlift[u][i].first) {
        for (auto [L, R]:binlift[u][i].second) add(U, {L, R});
        u = binlift[u][i].first;
        for (auto [L, R]:binlift[v][i].second) add(V, {L, R});
        v = binlift[v][i].first;
    }
    add(V, {fa[v], fa[v]});
    for (auto [L, R]:U) V.push_back({L, R});
    return V;
}

set<int> seg[maxN];
void build(int id, int l, int r) {
    seg[id].clear();
    if (l==r) return;
    int mid = (l+r)/2;
    build(id*2, l, mid); build(id*2+1, mid+1, r);
}
void update(int id, int l, int r, int findl, int findr, int val, bool add) {
    if (r<findl || findr<l) return;
    if (findl<=l && r<=findr) {
        if (add) seg[id].insert(val);
        else seg[id].erase(val);
        return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, findl, findr, val, add);
    update(id*2+1, mid+1, r, findl, findr, val, add);
}
vector<int> nxt;
void qry(int id, int l, int r, int target) {
    if (r<target || target<l) return;
    for (int i:seg[id]) nxt.push_back(i);
    if (l==r) return;
    int mid = (l+r)/2;
    qry(id*2, l, mid, target); qry(id*2+1, mid+1, r, target);
}

int S[maxn], T[maxn], vis[maxn], cur = 0;
bool die = false;
set<int> exist;

void dfs4(int u) {
    vis[u] = 1;
    // cout << u << endl;
    exist.erase(a[u].first);
    vector<pair<int,int>> path = PATH(a[u].first, a[u].second);
    // for (auto [L, R]:path) cout << L << " " << R << endl;
    for (auto [L, R]:path) {
        while (exist.size() > 0) {
            int v = *exist.lower_bound(L);
            if (v > R) break;
            v = S[v];
            if (!vis[v]) dfs4(v);
            else if (vis[v]==1) die = true;
        }
        update(1, 1, n, L, R, u, 0);
    }
    nxt.clear();
    qry(1, 1, n, a[u].second);
    sort(nxt.begin(), nxt.end()); nxt.erase(unique(nxt.begin(), nxt.end()), nxt.end());
    for (int v:nxt) {
        if (!vis[v]) dfs4(v);
        else if (vis[v]==1) die = true;
    }
    vis[u] = 2;
}

void solve() {
    cin >> n;
    for (int i=1;i<=n;i++) sz[i] = 0, adj[i].clear(), ADJ[i].clear();
    cnter = 0;
    for (int i=1;i<=n-1;i++) {
        int u, v;
        cin >> u >> v;
        ADJ[u].push_back(v);
        ADJ[v].push_back(u);
    }
    fa[1] = 0, d[1] = 0;
    dfs1(1); dfs2(1);
    for (int i=1;i<=n;i++) for (int j:ADJ[i]) adj[newid[i]].push_back(newid[j]);
    for (int i=1;i<=n;i++) for (int j=0;j<lgn;j++) binlift[i][j] = {-1, {}};
    dfs3(1);
    // for (int i=1;i<=n;i++) {
    //     cout << i << endl;
    //     for (int j=0;j<lgn;j++) if (binlift[i][j].second.size() > 0) cout << binlift[i][j].second.back().first << " " << binlift[i][j].second.back().second << endl;
    // }
    exist.clear();
    build(1, 1, n);
    for (int i=1;i<=n;i++) S[i] = -1, T[i] = -1;
    cin >> m;
    for (int i=1;i<=m;i++) {
        int s, t;
        cin >> s >> t;
        s = newid[s], t = newid[t];
        a[i] = {s, t};
        S[s] = T[t] = i;
        exist.insert(a[i].first);
        vector<pair<int,int>> path = PATH(a[i].first, a[i].second);
        for (auto [L, R]:path) update(1, 1, n, L, R, i, 1);
    }
    for (int i=1;i<=m;i++) vis[i] = 0;
    die = false;
    for (int i=1;i<=m;i++) if (!vis[i]) dfs4(i);
    if (die) cout << "No\n";
    else cout << "Yes\n";
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
}

Compilation message (stderr)

jail.cpp: In function 'void dfs1(long long int)':
jail.cpp:30:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int j=1;j<ADJ[u].size();j++) if (sz[ADJ[u][j]] > sz[ADJ[u][0]]) swap(ADJ[u][0], ADJ[u][j]);
      |                  ~^~~~~~~~~~~~~~
jail.cpp: In function 'std::vector<std::pair<long long int, long long int> > PATH(long long int, long long int)':
jail.cpp:63:56: warning: self-comparison always evaluates to false [-Wtautological-compare]
   63 |     for (int i=lgn-1;i>=0;i--) if (binlift[u][i].first != binlift[u][i].first) {
      |                                    ~~~~~~~~~~~~~~~~~~~ ^~ ~~~~~~~~~~~~~~~~~~~

• 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