QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#663094 | #3501. Jail | KiharaTouma | 0 | 148ms | 711740kb | C++14 | 4.4kb | 2024-10-21 13:04:48 | 2024-10-21 13:04:50 |
Judging History
answer
//qoj3501
#include <bits/stdc++.h>
using namespace std;
const int N = 120010, M = 3e7 + 10;
int Tt, n, m, tot;
vector<int> g[N], h[M];
int anc[N][20], dep[N], vs[N], ind[M];
int id[N][20], ask[N], S[N], T[N];
int GL = 19;
void dfs(int x, int fa){
dep[x] = dep[fa] + 1;
anc[x][0] = fa;
id[x][0] = x;
// printf("[[%d %d\n", x, anc[3][0]);
for(int i = 1; i <= GL; ++ i){
anc[x][i] = anc[anc[x][i-1]][i-1];
if(anc[x][i]){
id[x][i] = ++ tot;
h[id[x][i-1]].push_back(id[x][i]);
h[id[anc[x][i-1]][i-1]].push_back(id[x][i]);
// printf("%d %d\n", id[x][i-1], id[x][i]);
// printf("%d %d\n", id[anc[x][i-1]][i-1], id[x][i]);
}
}
for(int i : g[x]){
if(i != fa){
dfs(i, x);
}
}
}
int lca(int x, int y, int p){
if(dep[x] > dep[y]){
swap(x, y);
}
for(int i = GL; i >= 0; -- i){
if(dep[anc[y][i]] >= dep[x]){
// printf("%d %d\n", id[y][i], p);
h[id[y][i]].push_back(p);
y = anc[y][i];
}
// printf("jmp %d %d %d %d\n", y, i, anc[y][i], x);
}
if(x == y){
// printf("%d %d\n", x, p);
h[x].push_back(p);
return x;
}
// printf("now %d %d\n", x, y);
for(int i = GL; i >= 0; -- i){
if(anc[x][i] != anc[y][i]){
// printf("%d %d\n", id[x][i], p);
// printf("%d %d\n", id[y][i], p);
h[id[x][i]].push_back(p);
h[id[y][i]].push_back(p);
x = anc[x][i];
y = anc[y][i];
}
}
// printf("-%d %d\n", x, p);
// printf("--%d %d\n", y, p);
// printf("---%d %d\n", anc[x][0], p);
h[x].push_back(p);
h[y].push_back(p);
h[anc[x][0]].push_back(p);
return anc[x][0];
}
int jmp(int x, int p){
if(p < 0) return -1;
for(int i = 19; i >= 0; -- i){
if(p & (1 << i)) x = anc[x][i];
}
return x;
}
void CLR(){
/*
int Tt, n, m, tot;
vector<int> g[N], h[M];
int anc[N][20], dep[N], vs[N], ind[M];
int id[N][20], ask[N], S[N], T[N];
int GL = 19;
*/
for(int i = 1; i <= n; ++ i){
vector<int> ().swap(g[i]);
memset(anc[i], 0, sizeof(anc[i]));
memset(id[i], 0, sizeof(id[i]));
dep[i] = vs[i] = 0;
}
for(int i = 1; i <= tot; ++ i){
vector<int> ().swap(h[i]);
ind[i] = 0;
}
tot = 0;
}
int main(){
scanf("%d", &Tt);
while(Tt--){
scanf("%d", &n);
tot = n;
for(int i = 1; i < n; ++ i){
int x, y;
scanf("%d%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
scanf("%d", &m);
bool flg = 1;
for(int i = 1; i <= m; ++ i){
scanf("%d%d", &S[i], &T[i]);
vs[T[i]] = 1;
if(S[i] != T[i]){
flg = 0;
}
}
if(m == n){
puts(flg ? "Yes" : "No");
CLR();
continue;
}
int st = 0;
for(int i = 1; i <= n; ++ i){
if(!vs[i]){
st = i;
}
}
// st = 1;
dfs(st, 0);
for(int i = 1; i <= m; ++ i){
ask[i] = ++ tot;
h[ask[i]].push_back(T[i]);
int k = anc[T[i]][0];
if(jmp(S[i], dep[S[i]]-dep[T[i]]) == T[i]){
k = jmp(S[i], dep[S[i]]-dep[T[i]]-1);
}
// printf("%d %d\n", S[i], k);
int l = lca(S[i], k, ask[i]);
}
queue<int> q;
for(int i = 1; i <= tot; ++ i){
for(int j : h[i]){
++ ind[j];
}
}
for(int i = 1; i <= tot; ++ i){
if(!ind[i]){
q.push(i);
}
}
while(!q.empty()){
int x = q.front();
q.pop();
for(int i : h[x]){
-- ind[i];
// printf("%d %d %d\n", x, i, ind[i]);
if(!ind[i]){
q.push(i);
}
}
}
flg = 0;
for(int i = 1; i <= tot; ++ i){
if(ind[i]){
flg = 1;
}
}
puts(flg ? "No" : "Yes");
CLR();
}
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: 100ms
memory: 711132kb
input:
1 2 1 2 2 1 2 2 1
output:
No
result:
ok single line: 'No'
Test #2:
score: 0
Wrong Answer
time: 148ms
memory: 711740kb
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 Yes Yes No No Yes No No Yes Yes Yes Yes No No No Yes Yes Yes Yes Yes No Yes Yes No Yes Yes Yes No No Yes Yes Yes Yes Yes Yes No No No No No No No No No No No No No No Yes Yes Yes No Yes Yes No Yes Yes No Yes Yes No Yes Yes No No Yes Yes No No Yes No No Yes No Yes Yes No Yes ...
result:
wrong answer 8th lines differ - expected: 'No', found: 'Yes'
Subtask #2:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 111ms
memory: 710152kb
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 Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes
result:
wrong answer 4th lines differ - expected: 'No', found: 'Yes'
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: 144ms
memory: 710460kb
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 Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes...
result:
wrong answer 24th lines differ - expected: 'No', found: 'Yes'
Subtask #7:
score: 0
Skipped
Dependency #1:
0%