| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 777908 |
2023-07-09T22:20:24 Z |
aZvezda |
Jail (JOI22_jail) |
C++14 |
|
5000 ms |
596 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
#ifndef LOCAL
#define cerr if(false)cerr
#endif
const int MAX_N = 2e3 + 10, LOG = 20;
int n, m, par[MAX_N][LOG], d[MAX_N], in[MAX_N], out[MAX_N], tme;
int sz[MAX_N], chain[MAX_N];
pair<int, int> quer[MAX_N];
vector<int> g[MAX_N], eul;
void calc(int x, int p) {
sz[x] = 1;
d[x] = d[p] + 1;
par[x][0] = p;
for(int i = 1; i < LOG; i ++) {
par[x][i] = par[par[x][i - 1]][i - 1];
}
for(auto it : g[x]) {
if(it == p) { continue; }
calc(it, x);
sz[x] += sz[it];
}
}
void dfs(int x, int p, bool big = false) {
if(big) {
chain[x] = chain[p];
} else {
chain[x] = x;
}
in[x] = eul.size();
eul.push_back(x);
int heavy = -1;
for(auto it : g[x]) {
if(it == p) { continue; }
if(heavy == -1 || sz[it] > sz[heavy]) {
heavy = it;
}
}
if(heavy != -1) { dfs(heavy, x, true); }
for(auto it : g[x]) {
if(it == p || it == heavy) { continue; }
dfs(it, x, false);
}
out[x] = eul.size() - 1;
}
int lca(int a, int b) {
if(d[a] < d[b]) { swap(a, b); }
for(int i = LOG - 1; i >= 0; i --) {
if(d[par[a][i]] >= d[b]) {
a = par[a][i];
}
}
if(a == b) { return a; }
for(int i = LOG - 1; i >= 0; i --) {
if(par[a][i] != par[b][i]) {
a = par[a][i];
b = par[b][i];
}
}
return par[a][0];
}
struct node_sim {
pair<int, int> mn, mx;
node_sim() { mn = {mod, -1}; mx = {-mod, -1}; }
node_sim(const pair<int, int> &x) { mn = mx = x; }
node_sim operator +(const node_sim &other) const {
node_sim ret;
ret.mn = mn.first < other.mn.first ? mn : other.mn;
ret.mx = mx.first > other.mx.first ? mx : other.mx;
return ret;
}
};
struct node_ex {
int val;
node_ex(const pair<int, int> &_val = {-1, -1}) { val = _val.first; }
node_ex operator +(const node_ex &other) const {
node_ex ret;
ret.val = val != -1 ? val : other.val;
return ret;
}
};
template<class node>
struct seg_tree {
node tree[4 * MAX_N];
void upd(int curr, int l, int r, int ind, const pair<int, int> &val = {-1, -1}) {
if(l == r && l == ind) {
if(val.first == -1) {
tree[curr] = node();
} else {
tree[curr] = node(val);
}
return;
} else if(l > ind || r < ind) { return; }
int m = (l + r) / 2ll;
upd(curr * 2, l, m, ind, val);
upd(curr * 2 + 1, m + 1, r, ind, val);
tree[curr] = tree[curr * 2] + tree[curr * 2 + 1];
}
node ans(int curr, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) {
return tree[curr];
} else if(l > qr || r < ql) { return node(); }
int m = (l + r) / 2ll;
return ans(curr * 2, l, m, ql, qr) + ans(curr * 2 + 1, m + 1, r, ql, qr);
}
};
seg_tree<node_sim> st;
seg_tree<node_ex> st_ex;
vector<int> ret = {};
vector<int> who[MAX_N];
int used[MAX_N];
int find_block(int a, int b) {
node_ex ans;
while(chain[a] != chain[b]) {
if(d[chain[a]] < d[chain[b]]) { swap(a, b); }
ans = ans + st_ex.ans(1, 0, MAX_N - 1, in[chain[a]], in[a]);
a = par[chain[a]][0];
}
if(d[a] > d[b]) { swap(a, b); }
ans = ans + st_ex.ans(1, 0, MAX_N - 1, in[a], in[b]);
return ans.val;
}
void topo(int x) {
if(used[x]) { return; }
used[x] = true;
int a = quer[x].first, b = quer[x].second;
st_ex.upd(1, 0, MAX_N - 1, in[a]);
for(auto it : who[b]) { topo(it); }
int bl;
while((bl = find_block(a, b)) != -1) {
st_ex.upd(1, 0, MAX_N - 1, in[quer[bl].first]);
topo(bl);
}
while(true) {
auto now = st.ans(1, 0, MAX_N - 1, in[b], out[b]);
if(now.mx.first > out[b]) {
st.upd(1, 0, MAX_N - 1, now.mx.second);
topo(now.mx.second);
} else if(now.mn.first < in[b]) {
st.upd(1, 0, MAX_N - 1, now.mn.second);
topo(now.mn.second);
} else {
break;
}
}
ret.push_back(x);
}
void reset() {
for(int i = 0; i <= n + 10; i ++) { st.upd(1, 0, MAX_N - 1, i); }
for(int i = 0; i <= n + 10; i ++) { st_ex.upd(1, 0, MAX_N - 1, i); }
}
void solve() {
reset();
eul.resize(0);
for(int i = 1; i <= n; i ++) {
who[i].resize(0);
g[i].resize(0);
}
fill_n(used, n + 1, false);
cin >> n;
for(int i = 0; i < n - 1; i ++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
calc(1, 0);
dfs(1, 0, false);
cin >> m;
for(int i = 0; i < m; i ++) {
int a, b;
cin >> a >> b;
quer[i] = {a, b};
who[lca(a, b)].push_back(i);
st.upd(1, 0, MAX_N - 1, in[a], {in[b], i});
st.upd(1, 0, MAX_N - 1, in[b], {in[a], i});
st_ex.upd(1, 0, MAX_N - 1, in[a], {i, -1});
}
ret = {};
for(int i = 0; i < m; i ++) {
if(!used[i]) {
topo(i);
}
}
reset();
for(int i = 0; i < m; i ++) {
int a = quer[i].first, b = quer[i].second;
st_ex.upd(1, 0, MAX_N - 1, in[a], {i, -1});
}
for(auto it : ret) {
int a = quer[it].first;
int b = quer[it].second;
st_ex.upd(1, 0, MAX_N - 1, in[a]);
if(find_block(a, b) != -1) {
cout << "No" << endl;
return;
}
st_ex.upd(1, 0, MAX_N - 1, in[b], {it, -1});
}
cout << "Yes" << endl;
}
signed main() {
// ios_base::sync_with_stdio(false); cin.tie(NULL);
int t;
cin >> t;
while(t --) {
solve();
}
}
Compilation message
jail.cpp: In function 'void solve()':
jail.cpp:217:26: warning: unused variable 'b' [-Wunused-variable]
217 | int a = quer[i].first, b = quer[i].second;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5034 ms |
596 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5031 ms |
564 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5031 ms |
564 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5031 ms |
564 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5031 ms |
564 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5054 ms |
468 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5034 ms |
596 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
