QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#876592 | #3501. Jail | eaten_book | 0 | 25ms | 19848kb | C++23 | 5.3kb | 2025-01-31 03:17:29 | 2025-01-31 03:17:30 |
Judging History
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;
}
详细
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%