QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#876592#3501. Jaileaten_book0 25ms19848kbC++235.3kb2025-01-31 03:17:292025-01-31 03:17:30

Judging History

This is the latest submission verdict.

  • [2025-01-31 03:17:30]
  • Judged
  • Verdict: 0
  • Time: 25ms
  • Memory: 19848kb
  • [2025-01-31 03:17:29]
  • 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;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

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: 18856kb

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: 3ms
memory: 18120kb

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: 25ms
memory: 19848kb

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%