QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#876839#3501. JailMispertion0 0ms0kbC++235.4kb2025-01-31 13:50:492025-01-31 13:50:49

Judging History

This is the latest submission verdict.

  • [2025-01-31 13:50:49]
  • Judged
  • Verdict: 0
  • Time: 0ms
  • Memory: 0kb
  • [2025-01-31 13:50:49]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

#define S second
#define F first
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define mispertion ios_base::sync_with_stdio(0),cin.tie(0)
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()

const ld PI = 3.1415926535;
const ld eps = 1e-9;
const int N = 2e5 + 2;
const int M = 1.5e6 + 13;
ll mod = 1e9+7;
const int infi = 1e9;
const ll infl = 1e16;
const int P = 31;

int mult(int a, int b) {
    return a * 1LL * b % mod; }

int sum(int a, int b) {
    if(a + b >= mod)
        return a + b - mod;
    if(a + b < 0)
        return a + b + mod;
    return a + b;
}

ll binpow(ll a, ll n) {
    if (n == 0) return 1;
    if (n % 2 == 1) {
        return binpow(a, n - 1) * a % (mod);
    } else {
        ll b = binpow(a, n / 2);
        return b * b % (mod);
    }
}

const int K = 19;
int n, m, s[N], t[N], sz[N], tin[N], tout[N], tick, par[N], h[N], d[N], her[N], cur;
int l[N * 15], r[N * 15], pss[N * 15], pst[N * 15], used[N * 15];
vector<int> g[N], ng[N * 15];

void precalc(int v, int p){
    par[v] = p;
    sz[v] = 1;
    for(auto u : g[v]){
        if(u == p) continue;
        d[u] = d[v] + 1;
        precalc(u, v);
        sz[v] += sz[u];
    }
    for(auto &u : g[v]){
        if(u == p) continue;
        if(g[v][0] == p || sz[g[v][0]] < sz[u]){
            swap(u, g[v][0]);
        }
    }
}

void dfs(int v, int r){
    tin[v] = ++tick;
    her[tin[v]] = v;
    h[v] = r;
    for(auto u : g[v]){
        if(u == par[v]) continue;
        dfs(u, (u == g[v][0] ? r : u));
    }
    tout[v] = tick;
}

bool ispar(int p, int v){
    return (tin[p] <= tin[v] && tout[v] <= tout[p]);
}

void buildd(int v, int tl, int tr){
    if(tl == tr){
        pst[her[tl]] = v;
        return;
    }
    int tm = (tl + tr) / 2;
    cur++;
    l[v] = cur;
    buildd(cur, tl, tm);
    cur++;
    r[v] = cur;
    buildd(cur, tm + 1, tr);
    ng[v].push_back(l[v]);
    ng[v].push_back(r[v]);
}

void buildu(int v, int tl, int tr){
    if(tl == tr){
        pss[her[tl]] = v;
        return;
    }
    int tm = (tl + tr) / 2;
    cur++;
    l[v] = cur;
    buildu(cur, tl, tm);
    cur++;
    r[v] = cur;
    buildu(cur, tm + 1, tr);
    ng[l[v]].push_back(v);
    ng[r[v]].push_back(v);
}

void addu(int v, int tl, int tr, int lg, int rg, int x){
    if(tl > rg || lg > tr)
        return;
    if(lg <= tl && tr <= rg){
        ng[v].push_back(x);
        return;
    }
    int tm = (tl + tr) / 2;
    addu(l[v], tl, tm, lg, rg, x);
    addu(r[v], tm + 1, tr, lg, rg, x);
}

void addd(int v, int tl, int tr, int lg, int rg, int x){
    if(tl > rg || lg > tr)
        return;
    if(lg <= tl && tr <= rg){
        ng[x].push_back(v);
        return;
    }
    int tm = (tl + tr) / 2;
    addd(l[v], tl, tm, lg, rg, x);
    addd(r[v], tm + 1, tr, lg, rg, x);
}

int check(int v){
    used[v] = 1;
    int ret = 1;
    for(auto u : ng[v]){
        if(used[u] == 1)
            return 0;
        if(!used[u])
            ret &= check(u);
    }
    used[v] = 2;
    return ret;
}

inline void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++)
        g[i].clear(), ng[i].clear();
    tick = 0;
    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    precalc(1, 1);
    dfs(min(n, 50), 1);
    cin >> m;
    for(int i = 1; i <= m; i++)
        cin >> s[i] >> t[i];
    cur = m + 1;
    int rd = cur;
    buildd(rd, 1, n);
    cur++;
    int ru = cur;
    buildu(ru, 1, n);
    for(int i = 1; i <= m; i++){
        ng[pst[t[i]]].push_back(i);
        ng[i].push_back(pss[s[i]]);
        int u = s[i], v = t[i];
        if(ispar(v, u)){
            for(auto e : g[v]){
                if(ispar(e, u)){
                    v = e;
                    break;
                }
            }
        }else{
            v = par[v];
        }
        while(h[v] != h[u]){
            if(d[h[v]] < d[h[u]]){
                swap(v, u);
            }
            addd(rd, 1, n, tin[h[v]], tin[v], i);
            v = par[h[v]];
        }
        if(d[v] < d[u])
            swap(u, v);
        addd(rd, 1, n, tin[u], tin[v], i);
        v = s[i], u = t[i];
        if(ispar(v, u)){
            for(auto e : g[v]){
                if(ispar(e, u)){
                    v = e;
                    break;
                }
            }
        }else{
            v = par[v];
        }
        while(h[v] != h[u]){
            if(d[h[v]] < d[h[u]]){
                swap(v, u);
            }
            addu(ru, 1, n, tin[h[v]], tin[v], i);
            v = par[h[v]];
        }
        if(d[v] < d[u])
            swap(u, v);
        addu(ru, 1, n, tin[u], tin[v], i);
    }
    int ans = 1;
    for(int i = 1; i <= cur; i++)
        used[i] = 0;
    for(int i = 1; i <= cur; i++)
        if(!used[i])
            ans &= check(i);
    for(int i = 1; i <= cur; i++)
        ng[i].clear();
    cout << (ans ? "Yes\n" : "No\n");
}

signed main() {
    mispertion;
    int t = 1;
    cin >> t;
    for(int i = 1; i <= t; i ++){
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

1
2
1 2
2
1 2
2 1

output:


result:


Subtask #2:

score: 0
Time Limit Exceeded

Test #21:

score: 0
Time Limit Exceeded

input:

20
250
1 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
3 23
1 24
24 25
25 26
5 26
1 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
7 42
2 43
43 44
44 45
45 46
4 46
2 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54
54 55
12 55
2 56
56 57
57 58
58 59
59 ...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Time Limit Exceeded

Test #66:

score: 0
Time Limit Exceeded

input:

1000
10
1 2
2 3
1 4
4 5
4 6
4 7
2 8
8 9
3 10
2
5 4
1 9
10
1 2
1 3
1 4
4 5
4 6
3 7
3 8
2 9
6 10
2
2 9
1 5
10
1 2
2 3
1 4
4 5
4 6
2 7
3 8
2 9
1 10
2
10 2
7 5
10
1 2
1 3
1 4
2 5
1 6
3 7
2 8
7 9
2 10
2
10 5
2 7
10
1 2
1 3
1 4
3 5
5 6
3 7
7 8
1 9
8 10
2
6 7
1 2
10
1 2
1 3
3 4
2 5
4 6
3 7
1 8
4 9
1 10
2
1...

output:


result:


Subtask #7:

score: 0
Skipped

Dependency #1:

0%