| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 567188 |
2022-05-23T08:59:35 Z |
tqbfjotld |
Jail (JOI22_jail) |
C++14 |
|
27 ms |
19672 KB |
#include <bits/stdc++.h>
using namespace std;
vector<int> adjl[120005];
int vis[400005];
int cur;
int fs[120005];
int ls[120005];
int A[120005];
int B[120005];
vector<int> adjl2[400005];
int curid = 0;
struct node{
int s,e,inid,outid;
node *l,*r;
vector<int> stuff;
node (int _s, int _e){
s = _s; e = _e;
inid = curid++;
outid = curid++;
if (s!=e){
l = new node(s,(s+e)/2);
r = new node((s+e)/2+1,e);
}
}
void add(int a, int b, int val){
if (a<=s && e<=b){
stuff.push_back(val);
return;
}
if (b<=(s+e)/2) l->add(a,b,val);
else if (a>(s+e)/2) r->add(a,b,val);
else {
l->add(a,b,val);
r->add(a,b,val);
}
}
void constructstuff(){
if (s!=e){
l->constructstuff();
r->constructstuff();
}
for (auto y : stuff){
adjl2[inid].push_back(y);
adjl2[y].push_back(outid);
}
}
void constructbef(int pos, int val){
adjl2[val].push_back(inid);
if (s==e) return;
if (pos<=(s+e)/2) l->constructbef(pos,val);
else r->constructbef(pos,val);
}
void constructaft(int pos, int val){
adjl2[outid].push_back(val);
if (s==e) return;
if (pos<=(s+e)/2) l->constructaft(pos,val);
else r->constructaft(pos,val);
}
}*root;
int p[120005];
int hd[120005];
int dep[120005];
int sz[120005];
int pre[120005];
int ct = 0;
void dfs(int nd){
sz[nd] = 1;
for (auto x : adjl[nd]){
if (x==p[nd]){
continue;
}
dep[x] = dep[nd]+1;
p[x] = nd;
dfs(x);
sz[nd] += sz[x];
}
}
void decomp(int nd, int head){
hd[nd] = head;
pre[nd] = ct++;
int mx = 0;
int mnd = -1;
for (auto x : adjl[nd]){
if (x==p[nd]) continue;
if (sz[x]>mx){
mx = sz[x];
mnd = x;
}
}
if (mnd==-1) return;
decomp(mnd,head);
for (auto x : adjl[nd]){
if (x==p[nd]||x==mnd) continue;
decomp(x,x);
}
}
bool checkcycle(int nd){
if (vis[nd]==2) return false;
vis[nd] = 1;
for (auto x : adjl2[nd]){
if (vis[x]==1) return true;
if (checkcycle(x)) return true;
}
vis[nd] = 2;
return false;
}
int p2[120005][20];
int anc(int a, int amt){
for (int x = 0; x<20; x++){
if ((1<<x)&amt){
a = p2[a][x];
}
}
return a;
}
int main(){
int Q;
scanf("%d",&Q);
while (Q--){
int n;
scanf("%d",&n);
ct = 0;
for (int x = 1; x<=n; x++){
adjl[x].clear();
}
for (int x = 0; x<n-1; x++){
int a,b;
scanf("%d%d",&a,&b);
adjl[a].push_back(b);
adjl[b].push_back(a);
}
p[1] = 0;
dfs(1);
decomp(1,1);
for (int x = 0; x<=n; x++){
p2[x][0] = p[x];
}
for (int x = 1; x<20; x++){
for (int y = 0; y<=n; y++){
p2[y][x] = p2[p2[y][x-1]][x-1];
}
}
int m;
scanf("%d",&m);
curid = m;
for (int x = 1; x<=n; x++){
fs[x] = -1;
ls[x] = -1;
}
for (int x = 0; x<m; x++){
scanf("%d%d",&A[x],&B[x]);
fs[A[x]] = x;
ls[B[x]] = x;
}
root = new node(0,n-1);
for (int x = 0; x<m; x++){
int a = A[x];
int b = B[x];
if (dep[a]>dep[b]) swap(a,b);
if (p[b]==a) continue;
if (anc(b,dep[b]-dep[a])==a){
a = anc(b,dep[b]-dep[a]-1);
b = p[b];
}
else{
a = p[a];
b = p[b];
}
while (hd[a]!=hd[b]){
if (dep[hd[a]]<dep[hd[b]]) swap(a,b);
root->add(pre[hd[a]],pre[a],x);
a = p[hd[a]];
}
if (pre[a]>pre[b])swap(a,b);
root->add(pre[a],pre[b],x);
}
for (int x = 0; x<3*n+5; x++){
adjl2[x].clear();
vis[x] = 0;
}
root->constructstuff();
for (int x = 1; x<=n; x++){
if (fs[x]!=-1 && ls[x]!=-1) adjl2[fs[x]].push_back(ls[x]);
if (fs[x]!=-1){
root->constructbef(pre[x],fs[x]);
}
if (ls[x]!=-1){
root->constructaft(pre[x],ls[x]);
}
}
bool ans = true;
for (int x = 0; x<curid; x++){
if (checkcycle(x)){
ans = false;
}
}
printf(ans?"Yes\n":"No\n");
}
}
Compilation message
jail.cpp: In function 'int main()':
jail.cpp:132:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
132 | scanf("%d",&Q);
| ~~~~~^~~~~~~~~
jail.cpp:135:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
135 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
jail.cpp:142:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
142 | scanf("%d%d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~
jail.cpp:160:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
160 | scanf("%d",&m);
| ~~~~~^~~~~~~~~
jail.cpp:167:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
167 | scanf("%d%d",&A[x],&B[x]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12500 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12500 KB |
Output is correct |
| 3 |
Correct |
6 ms |
12500 KB |
Output is correct |
| 4 |
Incorrect |
26 ms |
19672 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12500 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12500 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
13140 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12500 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12500 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
13140 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12500 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12500 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
13140 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12500 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12500 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
13140 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12500 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12576 KB |
Output is correct |
| 3 |
Correct |
7 ms |
12500 KB |
Output is correct |
| 4 |
Correct |
7 ms |
12500 KB |
Output is correct |
| 5 |
Incorrect |
27 ms |
15404 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12500 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12500 KB |
Output is correct |
| 3 |
Correct |
6 ms |
12500 KB |
Output is correct |
| 4 |
Incorrect |
26 ms |
19672 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
