QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#508115#3501. JailDimash0 40ms16564kbC++203.8kb2024-08-07 03:35:582024-08-07 03:35:58

Judging History

This is the latest submission verdict.

  • [2024-08-07 03:35:58]
  • Judged
  • Verdict: 0
  • Time: 40ms
  • Memory: 16564kb
  • [2024-08-07 03:35:58]
  • Submitted

answer

#include <bits/stdc++.h>

 
using namespace std;
    
typedef long long ll;
const int  N = 24e4 + 2, MOD = (int)1e9+7;

int n,x[N],y[N],m,it = 1,it1 = 1,s[N],f[N];
vector<int> g[N],G[N * 20];
int up[N][20],t[N][20],t1[N][20],tin[N],tout[N],timer = 0;
const int b = 18;
void dfs(int v,int pr) {
    tin[v] = ++timer;
    up[v][0] = pr;
    if(!x[v]) {
        t[v][0] = ++it;
    } else {
        t[v][0] = x[v];
    }
    if(!y[v]) {
        t1[v][0] = ++it;
    } else {
        t1[v][0] = y[v];
    }
    for(int i = 1;i <= b;i++) {
        up[v][i] = up[up[v][i-1]][i-1];
        t[v][i] = ++it;
        t1[v][i] = ++it;
        // cout << t[v][i] << ' ' << t[v][i - 1] << "\n" ;
        // cout << t[v][i] << ' ' << t[up[v][i-1]][i - 1] << '\n';
        G[t[v][i]].push_back(t[v][i-1]);G[t[v][i]].push_back(t[up[v][i-1]][i-1]);
        G[t1[v][i-1]].push_back(t1[v][i]);G[t1[up[v][i-1]][i-1]].push_back(t1[v][i]);
    }
    for(int to:g[v]) {
        if(to == pr) continue;
        dfs(to,v);
    }
    tout[v] = ++timer;
}
int vis[N * 20];
bool ans = 1;
void go(int v) {
    vis[v] = 1;
    for(int to:G[v]) {
        if(!vis[to]) {
            // cout << v << ' ' << to << '\n';
            go(to);
        } else {
            if(vis[to] == 1) {
                ans = 0;
            }
        }
    }
    vis[v] = 2;
}
bool is(int v,int u) {
    return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}
int lca(int v,int u) {
    if(is(v,u)) return v;
    if(is(u,v)) return u;
    for(int i = b;i >= 0;i--) {
        if(!is(up[v][i],u)) {
            v = up[v][i];
        }
    }
    return up[v][0];
}
void add(int v,int l,int id,bool ok = 1) {
    if(!is(l,v) || (ok && l == v)) return;
    // cout << v << ' ' << l << ' ' << id << '\n';
    for(int i = b;i >= 0;i--) {
        if(!is(up[v][i],l)) {
            // cout << id << ' ' << t[v][i] << '\n';
            G[id].push_back(t[v][i]);
            v = up[v][i];
        }
    }
    // cout << id << ' ' << t[v][1] << '\n';
    // cout << v << ' ' << l << '\n';
    if(ok)G[id].push_back(t[v][1]);
    else{
        G[id].push_back(t[v][0]);
        // cout << id << ' ' << t[v][0] << '\n';
    }
}
void add_(int v,int l,int id,bool ok = 1) {
    if(!is(l,v) || (l == v && ok)) return;
    // cout << v << ' ' << l << ' ' << id << ' ' << ok << '\n';
    // cout << v << ' ' << l << "x\n";
    for(int i = b;i >= 0;i--) {
        if(!is(up[v][i],l)) {
            // cout << t1[v][i] << ' ' << id << '\n';
            G[t1[v][i]].push_back(id);
            v = up[v][i];
        }
    }
    // cout << t1[v][1] << ' ' << id << '\n';
    // cout << "x\n";
    if(ok)G[t1[v][1]].push_back(id);
    else{
        G[t1[v][0]].push_back(id);
        // cout << t1[v][0] << ' ' << id << '\n';
    } 
}
void test() {
    ans = 1;
    timer = 0;
    cin >> n;
    for(int i = 1;i <= n;i++) {
        g[i].clear();
        x[i] = y[i] =0 ;
    }
    for(int i = 1;i <= n - 1;i++) {
        int a,b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    cin >> m;
    it = it1 = m;
    for(int i = 1;i <= m;i++) {
        cin >> s[i] >> f[i];
        y[f[i]] = x[s[i]] = i;
    }
    dfs(1,1);
    for(int i = 1;i <= m;i++) {
        int l = lca(s[i],f[i]);
        add(f[i],l,i,(s[i]!=l));add(up[s[i]][0],l,i,(s[i]!=l));
        add_(s[i],l,i,(f[i]!=l));add_(up[f[i]][0],l,i,(f[i]!=l));
    }
    for(int i = 1;i <= it;i++) {
        if(!vis[i]) {
            go(i);
        }
    }
    cout << (ans ? "Yes\n":"No\n");
    for(int i = 1;i <= it;i++) {
        G[i].clear();
        vis[i] =0;
    }
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    cin >> t;
    while(t--) {
        test();
    }
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 7ms
memory: 13868kb

input:

1
2
1 2
2
1 2
2 1

output:

No

result:

ok single line: 'No'

Test #2:

score: 0
Wrong Answer
time: 25ms
memory: 16252kb

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
Yes
No
Yes
No
Yes
No
Yes
No
No
Yes
No
No
No
No
No
No
No
No
No
Yes
Yes
Yes
Yes
No
No
Yes
No
No
No
No
No
No
No
Yes
Yes
No
Yes
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
Yes
No
Yes
Yes
No
Yes
No
No
Yes
Yes
No
Yes
Yes
No
No
Yes
Yes
No
No
Yes
No
No
Yes
No
No
Yes
No
No
Yes
No
No
No
Ye...

result:

wrong answer 42nd lines differ - expected: 'No', found: 'Yes'

Subtask #2:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 10ms
memory: 16564kb

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: 40ms
memory: 12316kb

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:

No
No
Yes
Yes
No
Yes
Yes
No
Yes
No
No
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
Yes
Yes
No
No
Yes
No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
Yes
No
No
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
Yes
Yes
Yes
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
No
No
Yes
Yes
No
Yes
No
No
No
No
Yes
Ye...

result:

wrong answer 1st lines differ - expected: 'Yes', found: 'No'

Subtask #7:

score: 0
Skipped

Dependency #1:

0%