# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
712926 |
2023-03-20T13:26:33 Z |
lam |
Jail (JOI22_jail) |
C++14 |
|
5000 ms |
3320 KB |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 2e4 + 10;
typedef pair<int,int> ii;
#define ff first
#define ss second
int n,m;
vector <int> adj[maxn];
int par[18][maxn];
int in[maxn],out[maxn],cnt;
bool dau[maxn];
vector <int> d;
ii num[maxn], a[maxn];
void dfs(int x, int p)
{
par[0][x]=p;
in[x]=++cnt;
for (int i=1; i<=17; i++) par[i][x]=par[i-1][par[i-1][x]];
for (int i:adj[x])
if (i!=p)
dfs(i,x);
out[x]=cnt;
}
bool check(int u, int v)
{
return in[u]<=in[v]&&out[v]<=out[u];
}
int lca(int u, int v)
{
if (check(u,v)) return u;
if (check(v,u)) return v;
for (int i=17; i>=0; i--)
if (!check(par[i][u],v)) u=par[i][u];
return par[0][u];
}
void upd(int u, int v, int type)
{
// int it=1;
while (v!=u)
{
// it++; if (it==10) break;
// cerr<<u<<' '<<v<<endl;
if (type==1) num[v].ff++;
else num[v].ss++;
v=par[0][v];
}
}
bool check_mid(int u, int v, int mid)
{
return check(u,mid)&&check(mid,v);
}
bool check_path(int u, int v, int x, int y)
{
/**
u x y v
**/
int p=lca(u,v);
if ((check_mid(p,u,x)||check_mid(p,v,x))&&(check_mid(p,u,y)||check_mid(p,v,y))) return 1;
return 0;
}
void xuly()
{
cin>>n;
for (int i=1; i<=n; i++) adj[i].clear(), in[i]=out[i]=0, num[i]={0,0}; cnt=0;
for (int i=1; i<n; i++)
{
int u,v; cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1,1);
cin>>m; d.clear();
for (int i=1; i<=m; i++) cin>>a[i].ff>>a[i].ss, d.push_back(i);
do
{
fill_n(dau,n+1,0);
for (int i=1; i<=m; i++) dau[a[i].ff] = 1;
// for (int i:d) cout<<i<<' '; cout<<'\n';
bool ccheck = 1;
for (int i:d)
{
int u = a[i].ff; int v=a[i].ss;
dau[u] = 0;
// for (int j=1; j<=n; j++) cout<<dau[j]<<' '; cout<<"!!\n";
int p=lca(u,v);
while (u!=p)
{
if (dau[u]) ccheck = 0;
u=par[0][u];
}
if (dau[p]) ccheck=0;
while (v!=p)
{
if (dau[v]) ccheck=0;
v=par[0][v];
}
dau[a[i].ss] = 1;
if (!ccheck) break;
}
if (!ccheck) continue;
cout<<"Yes\n";
return;
}
while (next_permutation(d.begin(),d.end()));
cout<<"No\n";
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int tt; cin>>tt;
while (tt--) xuly();
}
Compilation message
jail.cpp: In function 'void xuly()':
jail.cpp:64:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
64 | for (int i=1; i<=n; i++) adj[i].clear(), in[i]=out[i]=0, num[i]={0,0}; cnt=0;
| ^~~
jail.cpp:64:76: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
64 | for (int i=1; i<=n; i++) adj[i].clear(), in[i]=out[i]=0, num[i]={0,0}; cnt=0;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3156 KB |
Output is correct |
2 |
Correct |
2 ms |
3156 KB |
Output is correct |
3 |
Correct |
2 ms |
3156 KB |
Output is correct |
4 |
Correct |
10 ms |
3264 KB |
Output is correct |
5 |
Correct |
21 ms |
3316 KB |
Output is correct |
6 |
Correct |
2 ms |
3284 KB |
Output is correct |
7 |
Correct |
6 ms |
3284 KB |
Output is correct |
8 |
Execution timed out |
5091 ms |
3156 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3156 KB |
Output is correct |
2 |
Correct |
2 ms |
3156 KB |
Output is correct |
3 |
Correct |
3 ms |
3284 KB |
Output is correct |
4 |
Correct |
3 ms |
3284 KB |
Output is correct |
5 |
Correct |
3 ms |
3284 KB |
Output is correct |
6 |
Correct |
3 ms |
3288 KB |
Output is correct |
7 |
Correct |
3 ms |
3284 KB |
Output is correct |
8 |
Correct |
3 ms |
3284 KB |
Output is correct |
9 |
Correct |
3 ms |
3260 KB |
Output is correct |
10 |
Correct |
3 ms |
3320 KB |
Output is correct |
11 |
Correct |
3 ms |
3284 KB |
Output is correct |
12 |
Correct |
2 ms |
3284 KB |
Output is correct |
13 |
Correct |
2 ms |
3300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3156 KB |
Output is correct |
2 |
Correct |
2 ms |
3156 KB |
Output is correct |
3 |
Correct |
3 ms |
3284 KB |
Output is correct |
4 |
Correct |
3 ms |
3284 KB |
Output is correct |
5 |
Correct |
3 ms |
3284 KB |
Output is correct |
6 |
Correct |
3 ms |
3288 KB |
Output is correct |
7 |
Correct |
3 ms |
3284 KB |
Output is correct |
8 |
Correct |
3 ms |
3284 KB |
Output is correct |
9 |
Correct |
3 ms |
3260 KB |
Output is correct |
10 |
Correct |
3 ms |
3320 KB |
Output is correct |
11 |
Correct |
3 ms |
3284 KB |
Output is correct |
12 |
Correct |
2 ms |
3284 KB |
Output is correct |
13 |
Correct |
2 ms |
3300 KB |
Output is correct |
14 |
Correct |
2 ms |
3156 KB |
Output is correct |
15 |
Correct |
2 ms |
3156 KB |
Output is correct |
16 |
Correct |
7 ms |
3288 KB |
Output is correct |
17 |
Correct |
3 ms |
3284 KB |
Output is correct |
18 |
Correct |
6 ms |
3284 KB |
Output is correct |
19 |
Correct |
2 ms |
3156 KB |
Output is correct |
20 |
Correct |
4 ms |
3284 KB |
Output is correct |
21 |
Correct |
5 ms |
3284 KB |
Output is correct |
22 |
Correct |
5 ms |
3292 KB |
Output is correct |
23 |
Correct |
3 ms |
3156 KB |
Output is correct |
24 |
Correct |
3 ms |
3156 KB |
Output is correct |
25 |
Correct |
12 ms |
3288 KB |
Output is correct |
26 |
Correct |
4 ms |
3284 KB |
Output is correct |
27 |
Correct |
4 ms |
3284 KB |
Output is correct |
28 |
Correct |
8 ms |
3156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3156 KB |
Output is correct |
2 |
Correct |
2 ms |
3156 KB |
Output is correct |
3 |
Correct |
3 ms |
3284 KB |
Output is correct |
4 |
Correct |
3 ms |
3284 KB |
Output is correct |
5 |
Correct |
3 ms |
3284 KB |
Output is correct |
6 |
Correct |
3 ms |
3288 KB |
Output is correct |
7 |
Correct |
3 ms |
3284 KB |
Output is correct |
8 |
Correct |
3 ms |
3284 KB |
Output is correct |
9 |
Correct |
3 ms |
3260 KB |
Output is correct |
10 |
Correct |
3 ms |
3320 KB |
Output is correct |
11 |
Correct |
3 ms |
3284 KB |
Output is correct |
12 |
Correct |
2 ms |
3284 KB |
Output is correct |
13 |
Correct |
2 ms |
3300 KB |
Output is correct |
14 |
Correct |
2 ms |
3156 KB |
Output is correct |
15 |
Correct |
2 ms |
3156 KB |
Output is correct |
16 |
Correct |
7 ms |
3288 KB |
Output is correct |
17 |
Correct |
3 ms |
3284 KB |
Output is correct |
18 |
Correct |
6 ms |
3284 KB |
Output is correct |
19 |
Correct |
2 ms |
3156 KB |
Output is correct |
20 |
Correct |
4 ms |
3284 KB |
Output is correct |
21 |
Correct |
5 ms |
3284 KB |
Output is correct |
22 |
Correct |
5 ms |
3292 KB |
Output is correct |
23 |
Correct |
3 ms |
3156 KB |
Output is correct |
24 |
Correct |
3 ms |
3156 KB |
Output is correct |
25 |
Correct |
12 ms |
3288 KB |
Output is correct |
26 |
Correct |
4 ms |
3284 KB |
Output is correct |
27 |
Correct |
4 ms |
3284 KB |
Output is correct |
28 |
Correct |
8 ms |
3156 KB |
Output is correct |
29 |
Execution timed out |
5029 ms |
3284 KB |
Time limit exceeded |
30 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3156 KB |
Output is correct |
2 |
Correct |
2 ms |
3156 KB |
Output is correct |
3 |
Correct |
3 ms |
3284 KB |
Output is correct |
4 |
Correct |
3 ms |
3284 KB |
Output is correct |
5 |
Correct |
3 ms |
3284 KB |
Output is correct |
6 |
Correct |
3 ms |
3288 KB |
Output is correct |
7 |
Correct |
3 ms |
3284 KB |
Output is correct |
8 |
Correct |
3 ms |
3284 KB |
Output is correct |
9 |
Correct |
3 ms |
3260 KB |
Output is correct |
10 |
Correct |
3 ms |
3320 KB |
Output is correct |
11 |
Correct |
3 ms |
3284 KB |
Output is correct |
12 |
Correct |
2 ms |
3284 KB |
Output is correct |
13 |
Correct |
2 ms |
3300 KB |
Output is correct |
14 |
Correct |
2 ms |
3156 KB |
Output is correct |
15 |
Correct |
2 ms |
3156 KB |
Output is correct |
16 |
Correct |
7 ms |
3288 KB |
Output is correct |
17 |
Correct |
3 ms |
3284 KB |
Output is correct |
18 |
Correct |
6 ms |
3284 KB |
Output is correct |
19 |
Correct |
2 ms |
3156 KB |
Output is correct |
20 |
Correct |
4 ms |
3284 KB |
Output is correct |
21 |
Correct |
5 ms |
3284 KB |
Output is correct |
22 |
Correct |
5 ms |
3292 KB |
Output is correct |
23 |
Correct |
3 ms |
3156 KB |
Output is correct |
24 |
Correct |
3 ms |
3156 KB |
Output is correct |
25 |
Correct |
12 ms |
3288 KB |
Output is correct |
26 |
Correct |
4 ms |
3284 KB |
Output is correct |
27 |
Correct |
4 ms |
3284 KB |
Output is correct |
28 |
Correct |
8 ms |
3156 KB |
Output is correct |
29 |
Execution timed out |
5029 ms |
3284 KB |
Time limit exceeded |
30 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3156 KB |
Output is correct |
2 |
Correct |
2 ms |
3156 KB |
Output is correct |
3 |
Correct |
2 ms |
3156 KB |
Output is correct |
4 |
Correct |
2 ms |
3156 KB |
Output is correct |
5 |
Execution timed out |
5073 ms |
3228 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3156 KB |
Output is correct |
2 |
Correct |
2 ms |
3156 KB |
Output is correct |
3 |
Correct |
2 ms |
3156 KB |
Output is correct |
4 |
Correct |
10 ms |
3264 KB |
Output is correct |
5 |
Correct |
21 ms |
3316 KB |
Output is correct |
6 |
Correct |
2 ms |
3284 KB |
Output is correct |
7 |
Correct |
6 ms |
3284 KB |
Output is correct |
8 |
Execution timed out |
5091 ms |
3156 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |