| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 544562 |
2022-04-02T11:14:37 Z |
Rafi22 |
Jail (JOI22_jail) |
C++14 |
|
53 ms |
107476 KB |
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
const int N=120007;
vector<int>G[N];
int skok[N][17];
vector<int>G1[N*37];
int ile[N*37];
int pre[N],post[N],c;
int n;
void edge(int u,int v)
{
//cout<<u<<" "<<v<<endl;
G1[u].pb(v);
ile[v]++;
}
void dfs(int v,int o)
{
pre[v]=++c;
skok[v][0]=o;
edge(n+v,v);
edge(n+v,o);
edge(v+n*18,n+v+n*18);
edge(o+n*18,n+v+n*18);
for(int i=1;i<17;i++)
{
skok[v][i]=skok[skok[v][i-1]][i-1];
edge((i+1)*n+v,i*n+v);
edge((i+1)*n+v,i*n+skok[v][i-1]);
edge(i*n+v+n*18,(i+1)*n+v+n*18);
edge(i*n+skok[v][i-1]+n*18,(i+1)*n+v+n*18);
}
for(auto u:G[v])
{
if(u==o) continue;
dfs(u,v);
}
post[v]=c;
}
bool anc(int u,int v){return pre[u]<=pre[v]&&post[u]>=post[v];}
int lca(int u,int v)
{
if(anc(u,v)) return u;
for(int i=16;i>=0;i--) if(!anc(skok[u][i],v)) u=skok[u][i];
return skok[u][0];
}
int main()
{
freopen("01-09.in","r",stdin);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt,xd=0;
cin>>tt;
while(tt--)
{
int a,b,m;
cin>>n;
for(int i=1;i<n;i++)
{
cin>>a>>b;
G[a].pb(b);
G[b].pb(a);
}
c=0;
dfs(1,1);
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>a>>b;
edge(a,b);
edge(a+n*18,a);
int l=lca(a,b);
// cout<<l<<endl;
if(a!=l)
{
edge(a,l);
int x=skok[a][0];
if(x!=l&&skok[x][0]==l)
{
edge(a,x);
edge(x+n*18,a);
}
for(int j=16;j>=0;j--)
{
if(!anc(skok[x][j],l))
{
//cout<<"XD"<<skok[x][j]<<endl;
edge(a,(j+1)*n+x);
edge((j+1)*n+x+n*18,a);
x=skok[x][j];
}
}
}
if(b!=l)
{
edge(l+n*18,a);
int x=skok[b][0];
if(x!=l&&skok[x][0]==l)
{
edge(a,x);
edge(x+n*18,a);
}
for(int j=16;j>=0;j--)
{
if(!anc(skok[x][j],l))
{
edge(a,(j+1)*n+x);
edge((j+1)*n+x+n*18,a);
x=skok[x][j];
}
}
}
edge(a,b+n*18);
}
deque<int>Q;
for(int i=1;i<=n*36;i++) if(ile[i]==0) Q.pb(i);
int c=0;
while(sz(Q)>0)
{
int v=Q[0];
Q.pop_front();
c++;
for(auto u:G1[v])
{
ile[u]--;
if(ile[u]==0) Q.pb(u);
}
}
if(c==n*36) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
for(int i=1;i<=n;i++) G[i].clear();
for(int i=1;i<=n*36;i++)
{
ile[i]=0;
G1[i].clear();
}
}
return 0;
}
Compilation message
jail.cpp: In function 'int main()':
jail.cpp:70:12: warning: unused variable 'xd' [-Wunused-variable]
70 | int tt,xd=0;
| ^~
jail.cpp:66:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | freopen("01-09.in","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
107476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
107404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
107404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
107404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
107404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
107352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
107476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
