oj.uz

Submission #1000541

# Submission time Handle Problem Language Result Execution time Memory
1000541 2024-06-17T17:03:00 Z onbert Jail (JOI22_jail) C++17
0 / 100
 5000 ms 147180 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int maxn = 120005, maxN = 480005, lgn = 17, INF = 1e6;
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;

bool cmp(int &x, int &y) {
    return sz[x] > sz[y];
}

void dfs1(int u) {
    sz[u] = 1;
    for (int v:ADJ[u]) {
        ADJ[v].erase(find(ADJ[v].begin(), ADJ[v].end(), u));
        dfs1(v);
        sz[u] += sz[v];
    }
    sort(ADJ[u].begin(), ADJ[u].end(), cmp);
}
void dfs2(int u) {
    cnter++;
    newid[u] = cnter;
    for (int v:ADJ[u]) {
        d[cnter+1] = d[newid[u]] + 1;
        fa[cnter+1] = newid[u];
        dfs2(v);
    }
    lim[newid[u]] = cnter;
}

int skip[maxn];
void dfs3(int u) {
    for (int v:adj[u]) {
        if (v == adj[u][0]) skip[v] = skip[u];
        else skip[v] = v;
        dfs3(v);
    }
}

vector<pair<int,int>> path;
void PATH(int u, int v) {
    path.clear();
    int U = u, V = v;
    while (u!=v) {
        if (d[u] > d[v]) swap(u, v);
        path.push_back({skip[v], v});
        v = skip[v];
        if (v!=1) v = fa[v];
    }
    sort(path.rbegin(), path.rend());
    int siz = path.size();
    if (siz >= 2 && path[siz-1].first==path[siz-2].first) path.pop_back();
    auto [l, r] = path.back();
    while (l<r) {
        int mid = (l+r+1)/2;
        if (mid <= U && U <= lim[mid] && mid <= V && V <= lim[mid]) l = mid;
        else r = mid-1;
    }
    path.back().first = l;
}

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 addd) {
    if (r<findl || findr<l) return;
    if (findl<=l && r<=findr) {
        if (addd) seg[id].insert(val);
        else seg[id].erase(val);
        return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, findl, findr, val, addd);
    update(id*2+1, mid+1, r, findl, findr, val, addd);
}
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];
bool die = false;
set<int> exist;

void dfs4(int &u) {
    int s = a[u].first, t = a[u].second;
    vis[u] = 1;
    PATH(s, t);
    for (auto [L, R]:path) {
        int cur = L-1;
        while (exist.size() > 1) {
            cur = *exist.upper_bound(cur);
            if (cur > R) break;
            if (cur==s) continue;
            int v = S[cur];
            // cout << u << " " << v << endl;
            if (!vis[v]) dfs4(v);
            else if (vis[v]==1) die = true;
            if (die) return;
        }
    }
    nxt.clear();
    qry(1, 1, n, t);
    for (int v:nxt) if (v!=u) {
        // cout << u << " " << v << endl;
        if (!vis[v]) dfs4(v);
        else if (vis[v]==1) die = true;
        if (die) return;
    }
    for (auto [L, R]:path) update(1, 1, n, L, R, u, 0);
    exist.erase(s);
    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]);
    skip[1] = 1;
    dfs3(1);
    // PATH(4, 6);
    // for (auto [L, R]:path) cout << L << " " << R << endl;
    // return;
    exist = {INF};
    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(s);
        PATH(s, t);
        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) break;
    }
    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();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28504 KB Output is correct
2 Correct 13 ms 28684 KB Output is correct
3 Correct 11 ms 28508 KB Output is correct
4 Correct 18 ms 28948 KB Output is correct
5 Correct 26 ms 29324 KB Output is correct
6 Correct 13 ms 28764 KB Output is correct
7 Correct 13 ms 28764 KB Output is correct
8 Correct 15 ms 28760 KB Output is correct
9 Correct 41 ms 31316 KB Output is correct
10 Correct 54 ms 55056 KB Output is correct
11 Correct 20 ms 28672 KB Output is correct
12 Correct 47 ms 29688 KB Output is correct
13 Correct 146 ms 73304 KB Output is correct
14 Correct 116 ms 73960 KB Output is correct
15 Correct 387 ms 92788 KB Output is correct
16 Correct 992 ms 147180 KB Output is correct
17 Execution timed out 5056 ms 103640 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28508 KB Output is correct
2 Correct 12 ms 28504 KB Output is correct
3 Correct 13 ms 28760 KB Output is correct
4 Correct 13 ms 28664 KB Output is correct
5 Correct 14 ms 28508 KB Output is correct
6 Correct 13 ms 28512 KB Output is correct
7 Correct 13 ms 28508 KB Output is correct
8 Correct 12 ms 28508 KB Output is correct
9 Correct 13 ms 28520 KB Output is correct
10 Correct 13 ms 28764 KB Output is correct
11 Correct 14 ms 28764 KB Output is correct
12 Incorrect 13 ms 28508 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28508 KB Output is correct
2 Correct 12 ms 28504 KB Output is correct
3 Correct 13 ms 28760 KB Output is correct
4 Correct 13 ms 28664 KB Output is correct
5 Correct 14 ms 28508 KB Output is correct
6 Correct 13 ms 28512 KB Output is correct
7 Correct 13 ms 28508 KB Output is correct
8 Correct 12 ms 28508 KB Output is correct
9 Correct 13 ms 28520 KB Output is correct
10 Correct 13 ms 28764 KB Output is correct
11 Correct 14 ms 28764 KB Output is correct
12 Incorrect 13 ms 28508 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28508 KB Output is correct
2 Correct 12 ms 28504 KB Output is correct
3 Correct 13 ms 28760 KB Output is correct
4 Correct 13 ms 28664 KB Output is correct
5 Correct 14 ms 28508 KB Output is correct
6 Correct 13 ms 28512 KB Output is correct
7 Correct 13 ms 28508 KB Output is correct
8 Correct 12 ms 28508 KB Output is correct
9 Correct 13 ms 28520 KB Output is correct
10 Correct 13 ms 28764 KB Output is correct
11 Correct 14 ms 28764 KB Output is correct
12 Incorrect 13 ms 28508 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28508 KB Output is correct
2 Correct 12 ms 28504 KB Output is correct
3 Correct 13 ms 28760 KB Output is correct
4 Correct 13 ms 28664 KB Output is correct
5 Correct 14 ms 28508 KB Output is correct
6 Correct 13 ms 28512 KB Output is correct
7 Correct 13 ms 28508 KB Output is correct
8 Correct 12 ms 28508 KB Output is correct
9 Correct 13 ms 28520 KB Output is correct
10 Correct 13 ms 28764 KB Output is correct
11 Correct 14 ms 28764 KB Output is correct
12 Incorrect 13 ms 28508 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28504 KB Output is correct
2 Correct 15 ms 28800 KB Output is correct
3 Correct 12 ms 28508 KB Output is correct
4 Correct 13 ms 28700 KB Output is correct
5 Correct 21 ms 28640 KB Output is correct
6 Incorrect 13 ms 28504 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28504 KB Output is correct
2 Correct 13 ms 28684 KB Output is correct
3 Correct 11 ms 28508 KB Output is correct
4 Correct 18 ms 28948 KB Output is correct
5 Correct 26 ms 29324 KB Output is correct
6 Correct 13 ms 28764 KB Output is correct
7 Correct 13 ms 28764 KB Output is correct
8 Correct 15 ms 28760 KB Output is correct
9 Correct 41 ms 31316 KB Output is correct
10 Correct 54 ms 55056 KB Output is correct
11 Correct 20 ms 28672 KB Output is correct
12 Correct 47 ms 29688 KB Output is correct
13 Correct 146 ms 73304 KB Output is correct
14 Correct 116 ms 73960 KB Output is correct
15 Correct 387 ms 92788 KB Output is correct
16 Correct 992 ms 147180 KB Output is correct
17 Execution timed out 5056 ms 103640 KB Time limit exceeded
18 Halted 0 ms 0 KB -