oj.uz

Submission #986514

# Submission time Handle Problem Language Result Execution time Memory
986514 2024-05-20T17:38:48 Z ShaShi Jail (JOI22_jail) C++17
0 / 100
 46 ms 94420 KB 
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define kill(x) cout << x << endl, exit(0);
#define endl "\n"

 
using namespace std;
typedef long long ll;
typedef long double ld;
 

const int MAXN = (int)1e6 + 7;
const int MOD = 998244853;
const ll INF = (ll)1e18 + 7;


int t, n, m, q, tmp, tmp2, tmp3, tmp4, ans, k, u, v, w, flag, N, M;
int arr[MAXN], h[MAXN], st[MAXN], fn[MAXN], ind[MAXN], par[MAXN];
bool seen[MAXN];
vector<int> adj[MAXN], G[MAXN], ord, Ss[MAXN], T[MAXN];
vector<pii> edge;


void DFSsz(int v) {
    seen[v] = 1;

    for (int u:adj[v]) {
        if (seen[u]) continue;
        
        h[u] = h[v]+1; par[u] = v;

        DFSsz(u);
    }
}


inline void add_edge(int u, int v) {
    if (u == v) return;

    G[u].pb(v);
    edge.pb(mp(u, v));
}


inline void check(int ind, int v) {
    for (int x:Ss[v]) add_edge(x, ind);
    for (int x:T[v]) add_edge(ind, x);
}


inline void process(int ind, int u, int v) {
    if (h[u] > h[v]) swap(u, v);

    while (h[v] > h[u]) {
        check(ind, v); v = par[v];
    }

    while (u != v) {
        check(ind, u); check(ind, v);
        u = par[u]; v = par[v];
    }
}


void DFS(int v) {
    seen[v] = 1;

    for (int u:G[v]) if (!seen[u]) DFS(u);
    
    ord.pb(v);
}


void solve() {
    cin >> n;

    for (int i=1; i<=n; i++) adj[i].clear(), G[i].clear(), Ss[i].clear(), T[i].clear();
    edge.clear(); ord.clear(); fill(seen, seen+n+1, 0);
    fill(h, h+n+1, 0); fill(ind, ind+n+1, 0); fill(par, par+n+1, 0);


    for (int i=1; i<n; i++) {
        cin >> u >> v;

        adj[u].pb(v); adj[v].pb(u);
    }

    
    DFSsz(1);

    cin >> m;

    for (int i=1; i<=m; i++) {
        cin >> st[i] >> fn[i];

        Ss[st[i]].pb(i); T[fn[i]].pb(i);
    }

    for (int i=1; i<=m; i++) process(i, st[i], fn[i]);

    ord.clear(); fill(seen, seen+n+1, 0);

    for (int i=1; i<=m; i++) if (!seen[i]) DFS(i);
    for (int i=0; i<m; i++) ind[ord[i]] = i;

    for (auto cur:edge) {
        if (ind[cur.F] < ind[cur.S]) {
            cout << "No\n";
            return;
        }
    }

    cout << "Yes\n";
}


int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> t;

    while (t--) solve();

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94416 KB Output is correct
2 Correct 43 ms 94400 KB Output is correct
3 Incorrect 45 ms 94288 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94296 KB Output is correct
2 Incorrect 45 ms 94412 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94296 KB Output is correct
2 Incorrect 45 ms 94412 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94296 KB Output is correct
2 Incorrect 45 ms 94412 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94296 KB Output is correct
2 Incorrect 45 ms 94412 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94416 KB Output is correct
2 Correct 43 ms 94420 KB Output is correct
3 Correct 43 ms 94376 KB Output is correct
4 Incorrect 46 ms 94420 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94416 KB Output is correct
2 Correct 43 ms 94400 KB Output is correct
3 Incorrect 45 ms 94288 KB Output isn't correct
4 Halted 0 ms 0 KB -