| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 648105 |
2022-10-05T11:44:37 Z |
blue |
Jail (JOI22_jail) |
C++17 |
|
1 ms |
212 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;
const int lg = 17;
const int INF = 1'000'000;
int N;
int M;
vi* edge;
int ct;
vi ord;
vi ordind;
vvi anc;
vi depth;
vi subtree;
void dfs(int u)
{
ct++;
ord[ct] = u;
ordind[u] = ct;
for(int v : edge[u])
{
if(v == anc[u][0]) continue;
anc[v][0] = u;
depth[v] = 1 + depth[u];
dfs(v);
subtree[u] += subtree[v];
}
}
int ancestor(int u, int k)
{
for(int e = 0; e <= lg; e++)
if(k & (1 << e))
u = anc[u][e];
return u;
}
int lca(int u, int v)
{
if(depth[u] > depth[v]) swap(u, v);
v = ancestor(v, depth[v] - depth[u]);
if(u == v) return u;
for(int e = lg; e >= 0; e--)
{
if(anc[u][e] == anc[v][e]) continue;
u = anc[u][e];
v = anc[v][e];
}
return anc[u][0];
}
struct segtree1
{
vector< set<pii> > markers;
vpii bestmark;
segtree1()
{
markers = vector<set<pii>>(1+4*N);
bestmark = vector<pii>(1+4*N, {INF, -1});
}
void insert(int I, pii V, int i = 1, int l = 1, int r = N)
{
if(I < l || r < I) return;
else if(l == r)
{
markers[i].insert(V);
bestmark[i] = min(bestmark[i], V);
}
else
{
insert(I, V, 2*i, l, (l+r)/2);
insert(I, V, 2*i+1, (l+r)/2+1, r);
bestmark[i] = min({bestmark[i], bestmark[2*i], bestmark[2*i+1]});
}
}
void erase(int I, pii V, int i = 1, int l = 1, int r = N)
{
if(I < l || r < I) return;
else if(l == r)
{
markers[i].erase(V);
if(markers[i].empty()) bestmark[i] = {INF, -1};
else bestmark[i] = *markers[i].begin();
}
else
{
erase(I, V, 2*i, l, (l+r)/2);
erase(I, V, 2*i+1, (l+r)/2+1, r);
bestmark[i] = min(bestmark[2*i], bestmark[2*i+1]);
}
}
pii rangemin(int L, int R, int i = 1, int l = 1, int r = N)
{
if(R < l || r < L) return {INF, -1};
else if(L <= l && r <= R) return bestmark[i];
else return min(rangemin(L, R, 2*i, l, (l+r)/2), rangemin(L, R, 2*i+1, (l+r)/2+1, r));
}
};
struct segtree2
{
vector<set<pii>> markers;
segtree2()
{
markers = vector<set<pii>>(1+4*N);
}
void insert(int L, int R, pii V, int i = 1, int l = 1, int r = N)
{
if(R < l || r < L) return;
else if(L <= l && r <= R)
{
markers[i].insert(V);
}
else
{
insert(L, R, V, 2*i, l, (l+r)/2);
insert(L, R, V, 2*i+1, (l+r)/2+1, r);
}
}
void erase(int L, int R, pii V, int i = 1, int l = 1, int r = N)
{
if(R < l || r < L) return;
else if(L <= l && r <= R)
{
markers[i].erase(V);
}
else
{
erase(L, R, V, 2*i, l, (l+r)/2);
erase(L, R, V, 2*i+1, (l+r)/2+1, r);
}
}
pii pointmax(int I, int i = 1, int l = 1, int r = N)
{
pii curr = markers[i].empty() ? pii{-INF, -1} : *markers[i].rbegin();
if(l == r) return curr;
else if(I <= (l+r)/2) return max(curr, pointmax(I, 2*i, l, (l+r)/2));
else return max(curr, pointmax(I, 2*i+1, (l+r)/2+1, r));
}
};
vi S, T;
vi A;
segtree1 ST1;
segtree2 ST2;
bool cyclic;
void insert_prisoner(int j)
{
// cerr << "insert prisoner " << j << '\n';
ST1.insert(ordind[S[j]], {depth[A[j]], j});
ST1.insert(ordind[T[j]], {depth[A[j]], j});
ST2.insert(ordind[T[j]], ordind[T[j]] + subtree[T[j]] - 1, {depth[T[j]], j});
}
void erase_prisoner(int j)
{
// cerr << "erase prisoner " << j << '\n';
ST1.erase(ordind[S[j]], {depth[A[j]], j});
ST1.erase(ordind[T[j]], {depth[A[j]], j});
ST2.erase(ordind[T[j]], ordind[T[j]] + subtree[T[j]] - 1, {depth[T[j]], j});
}
vi dfsenter;
vi dfsexit;
void prisonerdfs(int u)
{
dfsenter[u] = 1;
bool usedfirst = 0;
bool usedS = 0;
erase_prisoner(u);
while(1)
{
pii vp;
if(!usedfirst)
{
// cerr << "type = 1\n";
vp = ST1.rangemin(ordind[S[u]], ordind[S[u]] + subtree[S[u]] - 1);
if(vp.first > depth[S[u]])
{
usedfirst = 1;
// cerr << "continuing\n";
continue;
}
}
else if(!usedS)
{
// cerr << "type = 2\n";
vp = ST2.pointmax(ordind[S[u]]);
if(vp.first < depth[A[u]])
{
usedS = 1;
// cerr << "continuing\n";
continue;
}
}
else
{
// cerr << "type = 3\n";
vp = ST2.pointmax(ordind[T[u]]);
if(vp.first < depth[A[u]])
{
// cerr << "breaking\n";
break;
}
}
int v = vp.second;
// cerr << "edge = " << u << " -> " << v << '\n';
if(dfsenter[v] && !dfsexit[v])
{
cyclic = 1;
return;
}
else if(dfsenter[v] && dfsexit[v])
{
;
}
else
{
insert_prisoner(u);
prisonerdfs(v);
erase_prisoner(u);
if(cyclic) return;
}
}
erase_prisoner(u);
dfsexit[u] = 1;
}
void run()
{
cin >> N;
edge = new vi[1+N];
for(int e = 1; e <= N-1; e++)
{
int a, b;
cin >> a >> b;
edge[a].push_back(b);
edge[b].push_back(a);
}
ct = 0;
ord = vi(1+N, 0);
ordind = vi(1+N, 0);
depth = vi(1+N, 0);
anc = vvi(1+N, vi(1+lg, 0));
subtree = vi(1+N, 1);
anc[1][0] = 0;
depth[1] = 1;
dfs(1);
for(int e = 1; e <= lg; e++)
{
for(int i = 0; i <= N; i++)
{
anc[i][e] = anc[ anc[i][e-1] ][e-1];
}
}
ST1 = segtree1();
ST2 = segtree2();
cyclic = 0;
cin >> M;
S = T = vi(1+M);
A = vi(1+M);
for(int j = 1; j <= M; j++)
{
cin >> S[j] >> T[j];
A[j] = lca(S[j], T[j]);
insert_prisoner(j);
}
dfsenter = dfsexit = vi(1+M, 0);
for(int i = 1; i <= M; i++)
{
if(dfsenter[i]) continue;
prisonerdfs(i);
if(cyclic) break;
}
if(cyclic) cout << "No\n";
else cout << "Yes\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
for(int t = 1; t <= T; t++)
{
run();
}
cout << "random string\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
