| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 876217 |
2023-11-21T12:49:35 Z |
simona1230 |
Jail (JOI22_jail) |
C++17 |
|
5 ms |
16476 KB |
#include <bits/stdc++.h>
using namespace std;
int q,n,m;
vector<int> v[120001];
vector<int> g[120001],o[120001];
int s[120001],f[120001];
int par[120001];
int nums[120001];
int numf[120001];
void read()
{
memset(nums,0,sizeof(nums));
memset(numf,0,sizeof(numf));
cin>>n;
for(int i=1; i<=n; i++)
v[i].clear();
for(int i=1; i<n; i++)
{
int a,b;
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
cin>>m;
for(int i=1; i<=m; i++)
{
cin>>s[i]>>f[i];
}
}
vector<int> p;
int jump[120001][21];
int used[120001];
int lvl[120001];
void dfs(int i)
{
used[i]=1;
for(int j=0; j<v[i].size(); j++)
{
int nb=v[i][j];
if(!used[nb])
{
par[nb]=i;
lvl[nb]=lvl[i]+1;
jump[nb][0]=i;
dfs(nb);
}
}
}
void prec()
{
for(int j=1; j<=20; j++)
for(int i=1; i<=n; i++)
jump[i][j]=jump[jump[i][j-1]][j-1];
}
int make_jump(int x,int k)
{
for(int i=20; i>=0; i--)
if(k&(1<<i))
x=jump[x][i];
return x;
}
int lca(int x,int y)
{
if(lvl[x]>lvl[y])swap(x,y);
y=make_jump(y,abs(lvl[y]-lvl[x]));
if(x==y)return x;
for(int i=20; i>=0; i--)
{
if(jump[x][i]!=jump[y][i])
{
x=jump[x][i];
y=jump[y][i];
}
}
return jump[x][0];
}
int ver;
vector<int> p1,p2;
void backtr(int i,int idx)
{
if(i==ver)return;
if(idx==1)p1.push_back(i);
else p2.push_back(i);
backtr(par[i],idx);
}
void gen(int a,int b)
{
p.clear();
ver=lca(a,b);
p1.clear();
p2.clear();
backtr(a,1);
backtr(b,2);
p=p1;
p.push_back(ver);
for(int i=p2.size()-1; i>=0; i--)
p.push_back(p2[i]);
}
int in[1001][1001];
int used1[120001];
stack<int> st;
void dfs1(int i)
{
used1[i]=1;
for(int j=0;j<g[i].size();j++)
{
int nb=g[i][j];
if(!used1[nb])
{
dfs1(nb);
}
}
st.push(i);
}
int used2[120001];
void dfs2(int i)
{
used2[i]=1;
for(int j=0;j<o[i].size();j++)
{
int nb=o[i][j];
if(!used2[nb])
{
dfs2(nb);
}
}
}
void solve()
{
bool pos=1;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
int l=lca(s[i],f[i]);
int l1=lca(s[i],s[j]);
int l2=lca(f[i],s[j]);
//cout<<l<<" "<<l1<<" "<<l2<<endl;
if(l1==s[j]&&l2==l||l1==l&&l2==s[j])
{
g[i].push_back(j);
//cout<<i<<" "<<j<<endl;
o[j].push_back(i);
}
l1=lca(s[i],f[j]);
l2=lca(f[i],f[j]);
if(l1==f[j]&&l2==l||l1==l&&l2==f[j])
{
g[j].push_back(i);
//cout<<j<<" "<<i<<endl;
o[i].push_back(j);
}
}
}
for(int i=1;i<=m;i++)
{
if(!used1[i])dfs1(i);
}
int cnt=0;
while(st.size())
{
int vr=st.top();
st.pop();
if(!used2[vr])
{
cnt++;
dfs2(vr);
}
}
if(cnt==m)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
int main()
{
cin>>q;
while(q--)
{
memset(used,0,sizeof(used));
read();
dfs(1);
prec();
solve();
//read();
//subt();
}
return 0;
}
Compilation message
jail.cpp: In function 'void dfs(int)':
jail.cpp:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int j=0; j<v[i].size(); j++)
| ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs1(int)':
jail.cpp:105:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int j=0;j<g[i].size();j++)
| ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs2(int)':
jail.cpp:119:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int j=0;j<o[i].size();j++)
| ~^~~~~~~~~~~~
jail.cpp: In function 'void solve()':
jail.cpp:139:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
139 | if(l1==s[j]&&l2==l||l1==l&&l2==s[j])
| ~~~~~~~~^~~~~~~
jail.cpp:147:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
147 | if(l1==f[j]&&l2==l||l1==l&&l2==f[j])
| ~~~~~~~~^~~~~~~
jail.cpp:130:10: warning: unused variable 'pos' [-Wunused-variable]
130 | bool pos=1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16476 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
16220 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16220 KB |
Output is correct |
| 2 |
Correct |
4 ms |
16476 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
16376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16220 KB |
Output is correct |
| 2 |
Correct |
4 ms |
16476 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
16376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16220 KB |
Output is correct |
| 2 |
Correct |
4 ms |
16476 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
16376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16220 KB |
Output is correct |
| 2 |
Correct |
4 ms |
16476 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
16376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16476 KB |
Output is correct |
| 2 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
16472 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16476 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
16220 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
