oj.uz

답안 #553267

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
553267 2022-04-25T09:56:39 Z tht2005 Jail (JOI22_jail) C++17
100 / 100
 1179 ms 282192 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 120005;
const int L = 17;

int cnt, s[N], t[N], tin[N], tout[N], p[N][L], e[N][L], f[N][L], c[N * L * 2];
vector<int> aj[N];
vector<int> ej[N * L * 2];

#define ae(u, v) {\
    ej[(u)].push_back((v));\
}

void dfs(int v, int p_) {
    tin[v] = ++(*tin);
    p[v][0] = p_;
    for(int i = 0, u; i + 1 < L && (u = p[v][i]) && p[u][i]; ++i) {
        p[v][i + 1] = p[u][i];
        if(e[v][i] && e[u][i]) {
            e[v][i + 1] = ++cnt;
            ae(e[v][i], cnt);
            ae(e[u][i], cnt);
        }
        else {
            e[v][i + 1] = e[v][i] | e[u][i];
        }
        if(f[v][i] && f[u][i]) {
            f[v][i + 1] = ++cnt;
            ae(cnt, f[v][i]);
            ae(cnt, f[u][i]);
        }
        else {
            f[v][i + 1] = f[v][i] | f[u][i];
        }
    }
    for(int u : aj[v]) {
        if(u == p_) continue;
        dfs(u, v);
    }
    tout[v] = (*tin);
}

int anc(int v, int u) {
    return tin[v] <= tin[u] && tout[u] <= tout[v];
}
int lca(int v, int u) {
    if(anc(v, u)) return v;
    if(anc(u, v)) return u;
    for(int i = L; i--; ) {
        if(p[v][i] && !anc(p[v][i], u)) {
            v = p[v][i];
        }
    }
    return p[v][0];
}

bool dfs(int v) {
    c[v] = 1;
    for(int u : ej[v]) {
        if(c[u] == 1 || (c[u] == 0 && dfs(u))) {
            return 1;
        }
    }
    c[v] = -1;
    return 0;
}

int main() {
    int _;
    scanf("%d", &_);
    while(_--) {
        int n;
        scanf("%d", &n);
        for(int i = 1; i < n; ++i) {
            int u, v;
            scanf("%d %d", &u, &v);
            aj[u].push_back(v);
            aj[v].push_back(u);
        }
        int m;
        scanf("%d", &m);
        for(int i = 1; i <= m; ++i) {
            scanf("%d %d", s + i, t + i);
            e[s[i]][0] = i;
            f[t[i]][0] = i;
        }
        cnt = m;
        dfs(1, 0);
        for(int i = 1; i <= m; ++i) {
            int x = lca(s[i], t[i]);
            int v;
            if(s[i] != x) {
                v = *p[s[i]];
                for(int j = L; j--; ) {
                    if(p[v][j] && !anc(p[v][j], x)) {
                        if(e[v][j]) {
                            ae(e[v][j], i);
                        }
                        if(f[v][j]) {
                            ae(i, f[v][j]);
                        }
                        v = p[v][j];
                    }
                }
                if(v && v != x) {
                    if((*e[v]) && (*e[v]) != i) {
                        ae(*e[v], i);
                    }
                    if((*f[v]) && (*f[v]) != i) {
                        ae(i, *f[v]);
                    }
                }
            }
            if(t[i] != x) {
                v = *p[t[i]];
                for(int j = L; j--; ) {
                    if(p[v][j] && !anc(p[v][j], x)) {
                        if(e[v][j]) {
                            ae(e[v][j], i);
                        }
                        if(f[v][j]) {
                            ae(i, f[v][j]);
                        }
                        v = p[v][j];
                    }
                }
                if(v && v != x) {
                    if((*e[v]) && (*e[v]) != i) {
                        ae(*e[v], i);
                    }
                    if((*f[v]) && (*f[v]) != i) {
                        ae(i, *f[v]);
                    }
                }
            }
            for(int u : { s[i], t[i], x }) {
                if((*e[u]) && (*e[u]) != i) {
                    ae(*e[u], i);
                }
                if((*f[u]) && (*f[u]) != i) {
                    ae(i, *f[u]);
                }
            }
        }
        bool cyc = 0;
        for(int i = 1; i <= cnt; ++i) {
            if(c[i] == 0 && dfs(i)) {
                cyc = 1;
                break;
            }
        }
        puts(cyc ? "No" : "Yes");
        for(int i = 1; i <= n; ++i) {
            memset(p[i], 0, sizeof(p[i]));
            memset(e[i], 0, sizeof(e[i]));
            memset(f[i], 0, sizeof(f[i]));
            aj[i].clear();
        }
        for(int i = 1; i <= cnt; ++i) {
            c[i] = 0;
            ej[i].clear();
        }
    }
    return 0;
}

Compilation message

jail.cpp: In function 'int main()':
jail.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d", &_);
      |     ~~~~~^~~~~~~~~~
jail.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
jail.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |             scanf("%d %d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~~
jail.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         scanf("%d", &m);
      |         ~~~~~^~~~~~~~~~
jail.cpp:85:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |             scanf("%d %d", s + i, t + i);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 98892 KB Output is correct
2 Correct 51 ms 98880 KB Output is correct
3 Correct 50 ms 98900 KB Output is correct
4 Correct 64 ms 99128 KB Output is correct
5 Correct 78 ms 98932 KB Output is correct
6 Correct 55 ms 99020 KB Output is correct
7 Correct 53 ms 99068 KB Output is correct
8 Correct 54 ms 99076 KB Output is correct
9 Correct 141 ms 105016 KB Output is correct
10 Correct 122 ms 137932 KB Output is correct
11 Correct 58 ms 99092 KB Output is correct
12 Correct 101 ms 100024 KB Output is correct
13 Correct 928 ms 256640 KB Output is correct
14 Correct 601 ms 257208 KB Output is correct
15 Correct 783 ms 255476 KB Output is correct
16 Correct 1148 ms 282192 KB Output is correct
17 Correct 612 ms 205368 KB Output is correct
18 Correct 926 ms 274792 KB Output is correct
19 Correct 604 ms 207432 KB Output is correct
20 Correct 478 ms 207692 KB Output is correct
21 Correct 678 ms 260144 KB Output is correct
22 Correct 527 ms 257412 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 98892 KB Output is correct
2 Correct 55 ms 98964 KB Output is correct
3 Correct 58 ms 99032 KB Output is correct
4 Correct 55 ms 98952 KB Output is correct
5 Correct 56 ms 99068 KB Output is correct
6 Correct 55 ms 98992 KB Output is correct
7 Correct 56 ms 99020 KB Output is correct
8 Correct 57 ms 99008 KB Output is correct
9 Correct 59 ms 99020 KB Output is correct
10 Correct 55 ms 99064 KB Output is correct
11 Correct 57 ms 99020 KB Output is correct
12 Correct 55 ms 98928 KB Output is correct
13 Correct 57 ms 99000 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 98892 KB Output is correct
2 Correct 55 ms 98964 KB Output is correct
3 Correct 58 ms 99032 KB Output is correct
4 Correct 55 ms 98952 KB Output is correct
5 Correct 56 ms 99068 KB Output is correct
6 Correct 55 ms 98992 KB Output is correct
7 Correct 56 ms 99020 KB Output is correct
8 Correct 57 ms 99008 KB Output is correct
9 Correct 59 ms 99020 KB Output is correct
10 Correct 55 ms 99064 KB Output is correct
11 Correct 57 ms 99020 KB Output is correct
12 Correct 55 ms 98928 KB Output is correct
13 Correct 57 ms 99000 KB Output is correct
14 Correct 57 ms 98924 KB Output is correct
15 Correct 54 ms 98892 KB Output is correct
16 Correct 54 ms 99000 KB Output is correct
17 Correct 56 ms 98964 KB Output is correct
18 Correct 60 ms 99068 KB Output is correct
19 Correct 53 ms 98936 KB Output is correct
20 Correct 54 ms 99020 KB Output is correct
21 Correct 54 ms 99016 KB Output is correct
22 Correct 54 ms 99012 KB Output is correct
23 Correct 53 ms 98968 KB Output is correct
24 Correct 52 ms 98900 KB Output is correct
25 Correct 54 ms 99000 KB Output is correct
26 Correct 54 ms 98924 KB Output is correct
27 Correct 54 ms 99016 KB Output is correct
28 Correct 50 ms 98864 KB Output is correct

Subtask #4
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 98892 KB Output is correct
2 Correct 55 ms 98964 KB Output is correct
3 Correct 58 ms 99032 KB Output is correct
4 Correct 55 ms 98952 KB Output is correct
5 Correct 56 ms 99068 KB Output is correct
6 Correct 55 ms 98992 KB Output is correct
7 Correct 56 ms 99020 KB Output is correct
8 Correct 57 ms 99008 KB Output is correct
9 Correct 59 ms 99020 KB Output is correct
10 Correct 55 ms 99064 KB Output is correct
11 Correct 57 ms 99020 KB Output is correct
12 Correct 55 ms 98928 KB Output is correct
13 Correct 57 ms 99000 KB Output is correct
14 Correct 57 ms 98924 KB Output is correct
15 Correct 54 ms 98892 KB Output is correct
16 Correct 54 ms 99000 KB Output is correct
17 Correct 56 ms 98964 KB Output is correct
18 Correct 60 ms 99068 KB Output is correct
19 Correct 53 ms 98936 KB Output is correct
20 Correct 54 ms 99020 KB Output is correct
21 Correct 54 ms 99016 KB Output is correct
22 Correct 54 ms 99012 KB Output is correct
23 Correct 53 ms 98968 KB Output is correct
24 Correct 52 ms 98900 KB Output is correct
25 Correct 54 ms 99000 KB Output is correct
26 Correct 54 ms 98924 KB Output is correct
27 Correct 54 ms 99016 KB Output is correct
28 Correct 50 ms 98864 KB Output is correct
29 Correct 55 ms 99188 KB Output is correct
30 Correct 57 ms 99004 KB Output is correct
31 Correct 59 ms 99168 KB Output is correct
32 Correct 53 ms 99020 KB Output is correct
33 Correct 55 ms 99028 KB Output is correct
34 Correct 56 ms 99020 KB Output is correct
35 Correct 55 ms 99108 KB Output is correct
36 Correct 59 ms 99020 KB Output is correct
37 Correct 54 ms 98960 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 98892 KB Output is correct
2 Correct 55 ms 98964 KB Output is correct
3 Correct 58 ms 99032 KB Output is correct
4 Correct 55 ms 98952 KB Output is correct
5 Correct 56 ms 99068 KB Output is correct
6 Correct 55 ms 98992 KB Output is correct
7 Correct 56 ms 99020 KB Output is correct
8 Correct 57 ms 99008 KB Output is correct
9 Correct 59 ms 99020 KB Output is correct
10 Correct 55 ms 99064 KB Output is correct
11 Correct 57 ms 99020 KB Output is correct
12 Correct 55 ms 98928 KB Output is correct
13 Correct 57 ms 99000 KB Output is correct
14 Correct 57 ms 98924 KB Output is correct
15 Correct 54 ms 98892 KB Output is correct
16 Correct 54 ms 99000 KB Output is correct
17 Correct 56 ms 98964 KB Output is correct
18 Correct 60 ms 99068 KB Output is correct
19 Correct 53 ms 98936 KB Output is correct
20 Correct 54 ms 99020 KB Output is correct
21 Correct 54 ms 99016 KB Output is correct
22 Correct 54 ms 99012 KB Output is correct
23 Correct 53 ms 98968 KB Output is correct
24 Correct 52 ms 98900 KB Output is correct
25 Correct 54 ms 99000 KB Output is correct
26 Correct 54 ms 98924 KB Output is correct
27 Correct 54 ms 99016 KB Output is correct
28 Correct 50 ms 98864 KB Output is correct
29 Correct 55 ms 99188 KB Output is correct
30 Correct 57 ms 99004 KB Output is correct
31 Correct 59 ms 99168 KB Output is correct
32 Correct 53 ms 99020 KB Output is correct
33 Correct 55 ms 99028 KB Output is correct
34 Correct 56 ms 99020 KB Output is correct
35 Correct 55 ms 99108 KB Output is correct
36 Correct 59 ms 99020 KB Output is correct
37 Correct 54 ms 98960 KB Output is correct
38 Correct 165 ms 104520 KB Output is correct
39 Correct 120 ms 138216 KB Output is correct
40 Correct 112 ms 104856 KB Output is correct
41 Correct 86 ms 101348 KB Output is correct
42 Correct 91 ms 103300 KB Output is correct
43 Correct 103 ms 103236 KB Output is correct
44 Correct 64 ms 99612 KB Output is correct
45 Correct 134 ms 129036 KB Output is correct
46 Correct 133 ms 129116 KB Output is correct
47 Correct 134 ms 133764 KB Output is correct
48 Correct 130 ms 133644 KB Output is correct
49 Correct 126 ms 130496 KB Output is correct
50 Correct 126 ms 129096 KB Output is correct
51 Correct 213 ms 150492 KB Output is correct
52 Correct 227 ms 154344 KB Output is correct
53 Correct 65 ms 101076 KB Output is correct
54 Correct 146 ms 129076 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 98908 KB Output is correct
2 Correct 52 ms 98964 KB Output is correct
3 Correct 54 ms 98960 KB Output is correct
4 Correct 50 ms 98904 KB Output is correct
5 Correct 58 ms 98948 KB Output is correct
6 Correct 53 ms 99044 KB Output is correct
7 Correct 55 ms 98956 KB Output is correct
8 Correct 54 ms 98948 KB Output is correct
9 Correct 52 ms 98912 KB Output is correct
10 Correct 53 ms 99116 KB Output is correct
11 Correct 51 ms 98908 KB Output is correct
12 Correct 53 ms 99020 KB Output is correct
13 Correct 75 ms 99520 KB Output is correct
14 Correct 89 ms 99820 KB Output is correct
15 Correct 86 ms 99544 KB Output is correct
16 Correct 144 ms 129748 KB Output is correct
17 Correct 281 ms 144608 KB Output is correct
18 Correct 504 ms 168420 KB Output is correct
19 Correct 146 ms 128916 KB Output is correct
20 Correct 151 ms 128268 KB Output is correct
21 Correct 147 ms 128412 KB Output is correct
22 Correct 239 ms 144376 KB Output is correct
23 Correct 234 ms 144324 KB Output is correct
24 Correct 234 ms 142656 KB Output is correct
25 Correct 220 ms 143296 KB Output is correct
26 Correct 239 ms 144848 KB Output is correct
27 Correct 256 ms 135260 KB Output is correct
28 Correct 251 ms 140088 KB Output is correct
29 Correct 255 ms 138276 KB Output is correct
30 Correct 184 ms 134824 KB Output is correct
31 Correct 179 ms 134660 KB Output is correct
32 Correct 188 ms 133896 KB Output is correct
33 Correct 191 ms 134388 KB Output is correct

Subtask #7
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 98892 KB Output is correct
2 Correct 51 ms 98880 KB Output is correct
3 Correct 50 ms 98900 KB Output is correct
4 Correct 64 ms 99128 KB Output is correct
5 Correct 78 ms 98932 KB Output is correct
6 Correct 55 ms 99020 KB Output is correct
7 Correct 53 ms 99068 KB Output is correct
8 Correct 54 ms 99076 KB Output is correct
9 Correct 141 ms 105016 KB Output is correct
10 Correct 122 ms 137932 KB Output is correct
11 Correct 58 ms 99092 KB Output is correct
12 Correct 101 ms 100024 KB Output is correct
13 Correct 928 ms 256640 KB Output is correct
14 Correct 601 ms 257208 KB Output is correct
15 Correct 783 ms 255476 KB Output is correct
16 Correct 1148 ms 282192 KB Output is correct
17 Correct 612 ms 205368 KB Output is correct
18 Correct 926 ms 274792 KB Output is correct
19 Correct 604 ms 207432 KB Output is correct
20 Correct 478 ms 207692 KB Output is correct
21 Correct 678 ms 260144 KB Output is correct
22 Correct 527 ms 257412 KB Output is correct
23 Correct 54 ms 98892 KB Output is correct
24 Correct 55 ms 98964 KB Output is correct
25 Correct 58 ms 99032 KB Output is correct
26 Correct 55 ms 98952 KB Output is correct
27 Correct 56 ms 99068 KB Output is correct
28 Correct 55 ms 98992 KB Output is correct
29 Correct 56 ms 99020 KB Output is correct
30 Correct 57 ms 99008 KB Output is correct
31 Correct 59 ms 99020 KB Output is correct
32 Correct 55 ms 99064 KB Output is correct
33 Correct 57 ms 99020 KB Output is correct
34 Correct 55 ms 98928 KB Output is correct
35 Correct 57 ms 99000 KB Output is correct
36 Correct 57 ms 98924 KB Output is correct
37 Correct 54 ms 98892 KB Output is correct
38 Correct 54 ms 99000 KB Output is correct
39 Correct 56 ms 98964 KB Output is correct
40 Correct 60 ms 99068 KB Output is correct
41 Correct 53 ms 98936 KB Output is correct
42 Correct 54 ms 99020 KB Output is correct
43 Correct 54 ms 99016 KB Output is correct
44 Correct 54 ms 99012 KB Output is correct
45 Correct 53 ms 98968 KB Output is correct
46 Correct 52 ms 98900 KB Output is correct
47 Correct 54 ms 99000 KB Output is correct
48 Correct 54 ms 98924 KB Output is correct
49 Correct 54 ms 99016 KB Output is correct
50 Correct 50 ms 98864 KB Output is correct
51 Correct 55 ms 99188 KB Output is correct
52 Correct 57 ms 99004 KB Output is correct
53 Correct 59 ms 99168 KB Output is correct
54 Correct 53 ms 99020 KB Output is correct
55 Correct 55 ms 99028 KB Output is correct
56 Correct 56 ms 99020 KB Output is correct
57 Correct 55 ms 99108 KB Output is correct
58 Correct 59 ms 99020 KB Output is correct
59 Correct 54 ms 98960 KB Output is correct
60 Correct 165 ms 104520 KB Output is correct
61 Correct 120 ms 138216 KB Output is correct
62 Correct 112 ms 104856 KB Output is correct
63 Correct 86 ms 101348 KB Output is correct
64 Correct 91 ms 103300 KB Output is correct
65 Correct 103 ms 103236 KB Output is correct
66 Correct 64 ms 99612 KB Output is correct
67 Correct 134 ms 129036 KB Output is correct
68 Correct 133 ms 129116 KB Output is correct
69 Correct 134 ms 133764 KB Output is correct
70 Correct 130 ms 133644 KB Output is correct
71 Correct 126 ms 130496 KB Output is correct
72 Correct 126 ms 129096 KB Output is correct
73 Correct 213 ms 150492 KB Output is correct
74 Correct 227 ms 154344 KB Output is correct
75 Correct 65 ms 101076 KB Output is correct
76 Correct 146 ms 129076 KB Output is correct
77 Correct 51 ms 98908 KB Output is correct
78 Correct 52 ms 98964 KB Output is correct
79 Correct 54 ms 98960 KB Output is correct
80 Correct 50 ms 98904 KB Output is correct
81 Correct 58 ms 98948 KB Output is correct
82 Correct 53 ms 99044 KB Output is correct
83 Correct 55 ms 98956 KB Output is correct
84 Correct 54 ms 98948 KB Output is correct
85 Correct 52 ms 98912 KB Output is correct
86 Correct 53 ms 99116 KB Output is correct
87 Correct 51 ms 98908 KB Output is correct
88 Correct 53 ms 99020 KB Output is correct
89 Correct 75 ms 99520 KB Output is correct
90 Correct 89 ms 99820 KB Output is correct
91 Correct 86 ms 99544 KB Output is correct
92 Correct 144 ms 129748 KB Output is correct
93 Correct 281 ms 144608 KB Output is correct
94 Correct 504 ms 168420 KB Output is correct
95 Correct 146 ms 128916 KB Output is correct
96 Correct 151 ms 128268 KB Output is correct
97 Correct 147 ms 128412 KB Output is correct
98 Correct 239 ms 144376 KB Output is correct
99 Correct 234 ms 144324 KB Output is correct
100 Correct 234 ms 142656 KB Output is correct
101 Correct 220 ms 143296 KB Output is correct
102 Correct 239 ms 144848 KB Output is correct
103 Correct 256 ms 135260 KB Output is correct
104 Correct 251 ms 140088 KB Output is correct
105 Correct 255 ms 138276 KB Output is correct
106 Correct 184 ms 134824 KB Output is correct
107 Correct 179 ms 134660 KB Output is correct
108 Correct 188 ms 133896 KB Output is correct
109 Correct 191 ms 134388 KB Output is correct
110 Correct 91 ms 99972 KB Output is correct
111 Correct 81 ms 99576 KB Output is correct
112 Correct 800 ms 250444 KB Output is correct
113 Correct 170 ms 134460 KB Output is correct
114 Correct 543 ms 192872 KB Output is correct
115 Correct 98 ms 129092 KB Output is correct
116 Correct 227 ms 146940 KB Output is correct
117 Correct 601 ms 181240 KB Output is correct
118 Correct 170 ms 129008 KB Output is correct
119 Correct 156 ms 128908 KB Output is correct
120 Correct 66 ms 103116 KB Output is correct
121 Correct 301 ms 152504 KB Output is correct
122 Correct 312 ms 150860 KB Output is correct
123 Correct 183 ms 136372 KB Output is correct
124 Correct 435 ms 179512 KB Output is correct
125 Correct 180 ms 136548 KB Output is correct
126 Correct 1179 ms 279068 KB Output is correct
127 Correct 452 ms 197176 KB Output is correct
128 Correct 417 ms 197460 KB Output is correct
129 Correct 511 ms 207164 KB Output is correct
130 Correct 423 ms 197376 KB Output is correct