Submission #1127016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127016		Yang8on	Jail (JOI22_jail)	C++20	61 / 100	5094 ms	26324 KiB

jail

#include <bits/stdc++.h>
#define Y8o "Jail"
#define maxn (int) 2e5 + 5
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)
#define all(x) x.begin(), x.end()
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define fi(i, a, b) for(int i = a; i <= b; i ++)
#define fid(i, a, b) for(int i = a; i >= b; i --)

//#define f first
//#define s second

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r) (rng);
}
void iof() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
    if(fopen(Y8o".inp", "r"))
    {
        freopen(Y8o".inp", "r", stdin);
//        freopen(Y8o".out", "w", stdout);
    }
}
void ctime() {
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}


bool ok = 1;
int n, m;
vector<int> o[maxn];
pii qr[maxn];
int h[maxn], cha[maxn][18];
int dd[maxn];

void pre_dfs(int u = 1, int p = 0) {
    for(int v : o[u]) if(v != p) {
        h[v] = h[u] + 1, cha[v][0] = u;
        fi(i, 1, 17) cha[v][i] = cha[ cha[v][i - 1] ][i - 1];
        pre_dfs(v, u);
    }
}
int lca(int u, int v) {
    if(h[u] < h[v]) swap(u, v);
    int kc = h[u] - h[v];
    fid(i, 17, 0) if(gb(kc, i)) u = cha[u][i];
    fid(i, 17, 0) if(cha[u][i] != cha[v][i]) u = cha[u][i], v = cha[v][i];
    return u == v ? u : cha[u][0];
}

bool check(int x, int u, int v) {
    int p = lca(u, v);
    int pu = lca(u, x);
    int pv = lca(x, v);
    if( (pu == x && pv == p) ||
        (pv == x && pu == p) ) return true;
    return false;
}

void add_edge(int i, int j) {
    auto [u, v] = qr[i];
    auto [u2, v2] = qr[j];
    if(check(v2, u, v) || check(u, u2, v2)) o[i].push_back(j);
}

void dfs(int u) {
    dd[u] = 1;
    for(int v : o[u]) {
        if(!dd[v]) dfs(v);
        else if(dd[v] == 1) {
            ok = 0; return;
        }
    }
    dd[u] = 2;
}

void solve() {
    cin >> n, ok = 1;
    fi(i, 1, n - 1) {
        int u, v; cin >> u >> v;
        o[u].push_back(v), o[v].push_back(u);
    }
    cin >> m ;
    fi(i, 1, m) {
        int u, v; cin >> u >> v;
        qr[i] = { u, v };
    }

    pre_dfs();
    fi(i, 1, n) o[i].clear();
    fi(i, 1, m) {
        auto [u, v] = qr[i];
        fi(j, 1, m) if(i != j) {
            add_edge(i, j);
        }
    }
    fi(i, 1, n) if(!dd[i]) {
        dfs(i);
    }

    if(ok) cout << "Yes" << '\n';
    else cout << "No" << '\n';

    ok = 1;
    fi(i, 1, n) o[i].clear(), dd[i] = 0;
}


int main() {
    iof();

    int nTest = 1;
    cin >> nTest;

    while(nTest --) {
        solve();
    }

    ctime();
    return 0;
}

Compilation message (stderr)

jail.cpp: In function 'void iof()':
jail.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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