QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#876593#3501. JailMispertion0 28ms23924kbC++235.3kb2025-01-31 03:18:042025-01-31 03:18:05

Judging History

This is the latest submission verdict.

  • [2025-01-31 03:18:05]
  • Judged
  • Verdict: 0
  • Time: 28ms
  • Memory: 23924kb
  • [2025-01-31 03:18:04]
  • 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(1, 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);
    cout << (ans ? "Yes\n" : "No\n");
}

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

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 3ms
memory: 18176kb

input:

1
2
1 2
2
1 2
2 1

output:

No

result:

ok single line: 'No'

Test #2:

score: 0
Wrong Answer
time: 13ms
memory: 20896kb

input:

462
120
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 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
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 ...

output:

No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No...

result:

wrong answer 3rd lines differ - expected: 'Yes', found: 'No'

Subtask #2:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 4ms
memory: 18248kb

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:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No

result:

wrong answer 7th lines differ - expected: 'Yes', found: 'No'

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
Wrong Answer

Test #66:

score: 0
Wrong Answer
time: 28ms
memory: 23924kb

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:

Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
N...

result:

wrong answer 3rd lines differ - expected: 'Yes', found: 'No'

Subtask #7:

score: 0
Skipped

Dependency #1:

0%