QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#508115 | #3501. Jail | Dimash | 0 | 40ms | 16564kb | C++20 | 3.8kb | 2024-08-07 03:35:58 | 2024-08-07 03:35:58 |
Judging History
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();
}
}
Details
Tip: Click on the bar to expand more detailed information
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%