Submission #1300703

#TimeUsernameProblemLanguageResultExecution timeMemory
1300703baotoan655Jail (JOI22_jail)C++20
100 / 100
846 ms109276 KiB
#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;

const int N = 120005, LG = 18;
const int M = N * 5;
int n;
vector<int> g[N];
int dep[N], fa[N], head[N], sz[N], in[N], tim, tour[N], out[N];
vector<int> st[N], ed[N];
int up[N][LG];
int lc[M], rc[M];
vector<int> adj[M];
int numNode;
int build1(int l, int r) {
    int id = ++numNode;
    if(l == r) {
        for(int x : ed[tour[l]]) adj[id].emplace_back(x);
        return id;
    }
    int mid = (l + r) >> 1;
    lc[id] = build1(l, mid);
    rc[id] = build1(mid + 1, r);
    adj[id].emplace_back(lc[id]);
    adj[id].emplace_back(rc[id]);
    return id;
}
void update1(int k, int l, int r, int u, int v, int sus) {
    if(l > v || r < u) return;
    if(u <= l && r <= v) {
        adj[sus].emplace_back(k);
        return;
    }
    int mid = (l + r) >> 1;
    update1(lc[k], l, mid, u, v, sus);
    update1(rc[k], mid + 1, r, u, v, sus);
}
int build2(int l, int r) {
    int id = ++numNode;
    if(l == r) {
        for(int x : st[tour[l]]) adj[x].emplace_back(id);
        return id;
    }
    int mid = (l + r) >> 1;
    lc[id] = build2(l, mid);
    rc[id] = build2(mid + 1, r);
    adj[lc[id]].emplace_back(id);
    adj[rc[id]].emplace_back(id);
    return id;
}
void update2(int k, int l, int r, int u, int v, int sus) {
    if(l > v || r < u) return;
    if(u <= l && r <= v) {
        adj[k].emplace_back(sus);
        return;
    }
    int mid = (l + r) >> 1;
    update2(lc[k], l, mid, u, v, sus);
    update2(rc[k], mid + 1, r, u, v, sus);
}

void pdfs(int u) {
    sz[u] = 1;
    for(int v : g[u]) if(v != fa[u]) {
            dep[v] = dep[u] + 1;
            fa[v] = u;
            up[v][0] = u;
            for(int i = 1; i < LG; ++i) up[v][i] = up[up[v][i - 1]][i - 1];
            pdfs(v);
            sz[u] += sz[v];
        }
}
void hld(int u, int hd) {
    head[u] = hd;
    in[u] = ++tim;
    tour[tim] = u;
    int hc = -1;
    for(int v : g[u]) if(v != fa[u]) {
            if(hc == -1 || sz[v] > sz[hc]) hc = v;
        }
    if(hc != -1) hld(hc, hd);
    for(int v : g[u]) if(v != fa[u] && v != hc) hld(v, v);
    out[u] = tim;
}
bool isFa(int p, int u) {
    return in[p] < in[u] && in[u] <= out[p];
}
int r1, r2;

void add1(int i, int u, int v) {
    while(head[u] != head[v]) {
        if(dep[head[u]] < dep[head[v]]) swap(u, v);
        update1(r1, 1, n, in[head[u]], in[u], i);
        u = fa[head[u]];
    }
    if(dep[u] > dep[v]) swap(u, v);
    update1(r1, 1, n, in[u], in[v], i);
}
void add2(int i, int u, int v) {
    while(head[u] != head[v]) {
        if(dep[head[u]] < dep[head[v]]) swap(u, v);
        update2(r2, 1, n, in[head[u]], in[u], i);
        u = fa[head[u]];
    }
    if(dep[u] > dep[v]) swap(u, v);
    update2(r2, 1, n, in[u], in[v], i);
}
int jump(int u, int k) {
    for(int i = LG - 1; i >= 0; --i) if(k >> i & 1) u = up[u][i];
    return u;
}
void upd1(int i, int u, int v) {
    if(isFa(v, u)) {
        add1(i, u, jump(u, dep[u] - dep[v] - 1));
    } else {
        add1(i, u, fa[v]);
    }
}
void upd2(int i, int u, int v) {
    if(isFa(u, v)) {
        add2(i, jump(v, dep[v] - dep[u] - 1), v);
    } else add2(i, fa[u], v);
}
pair<int, int> Q[N];
int vis[M];
bool cyc;
void dfs(int u) {
//    cout << u << '\n';
    vis[u] = 1;
    for(int v : adj[u]) {
        if(vis[v] == 1) {
            cyc = true;
        }
        if(vis[v] == 0) dfs(v);
    }
    vis[u] = 2;
}
void solve() {
    cin >> n;
    for(int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    pdfs(1);
    hld(1, 1);
    int m;
    cin >> m;
    numNode = m;
    for(int i = 1; i <= m; ++i) {
        int s, t;
        cin >> s >> t;
        Q[i] = make_pair(s, t);
        st[s].emplace_back(i);
        ed[t].emplace_back(i);
    }
    r1 = build1(1, n);
    r2 = build2(1, n);
    for(int i = 1; i <= m; ++i) {
        upd1(i, Q[i].first, Q[i].second);
        upd2(i, Q[i].first, Q[i].second);
    }
    for(int i = 1; i <= numNode; ++i) {
        if(!vis[i]) dfs(i);
    }
    cout << (cyc ? "No" : "Yes") << '\n';

    cyc = false;
    tim = 0;
    for(int i = 1; i <= numNode; ++i) {
        adj[i].clear();
        vis[i] = 0;
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j < LG; ++j) up[i][j] = 0;
        g[i].clear();
        st[i].clear();
        ed[i].clear();
    }
    numNode = 0;
}

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

    file("A") else file("task");
    int tc;
    cin >> tc;
    for(int _ = 1; _ <= tc; ++_) solve();
    return 0;
}

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:2:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:188:5: note: in expansion of macro 'file'
  188 |     file("A") else file("task");
      |     ^~~~
jail.cpp:2:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:188:5: note: in expansion of macro 'file'
  188 |     file("A") else file("task");
      |     ^~~~
jail.cpp:2:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:188:20: note: in expansion of macro 'file'
  188 |     file("A") else file("task");
      |                    ^~~~
jail.cpp:2:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:188:20: note: in expansion of macro 'file'
  188 |     file("A") else file("task");
      |                    ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...