| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 570401 |
2022-05-29T13:22:20 Z |
jamezzz |
Jail (JOI22_jail) |
C++17 |
|
950 ms |
949980 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));
#define mod 1000000007
inline int add(int a,int b){
int r=a+b;
while(r>=mod)r-=mod;
while(r<0)r+=mod;
return r;
}
inline int mult(int a,int b){
return (int)(((ll)(a*b))%mod);
}
inline int rd(){
int x=0;
char ch=getchar_unlocked();
while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
x=(x<<3)+(x<<1)+(ch&15);
ch=getchar_unlocked();
}
return x;
}
#define maxn 120005
int n,m,s[maxn],t[maxn],sid[maxn],tid[maxn];
int par[maxn][20],snode[maxn][20],tnode[maxn][20],depth[maxn],cnt;
vi AL[maxn],AL2[maxn*50];
int vis[maxn*50];
bool pos=false;
void dfs(int u){
snode[u][0]=cnt++;
tnode[u][0]=cnt++;
if(sid[u]!=-1){
AL2[snode[u][0]].pb(sid[u]);
AL2[tnode[u][0]].pb(sid[u]);
//AL2[sid[u]].pb(snode[u][0]);
//AL2[sid[u]].pb(tnode[u][0]);
//pf("add: %d %d\n",sid[u],snode[u][0]);
}
if(tid[u]!=-1){
//AL2[snode[u][0]].pb(tid[u]);
//AL2[tnode[u][0]].pb(tid[u]);
AL[tid[u]].pb(snode[u][0]);
AL[tid[u]].pb(tnode[u][0]);
//pf("add: %d %d\n",tnode[u][0],tid[u]);
}
for(int v:AL[u]){
if(v==par[u][0])continue;
par[v][0]=u;
depth[v]=depth[u]+1;
dfs(v);
}
}
void dfs2(int u){
vis[u]=1;
for(int v:AL2[u]){
if(vis[v]==0)dfs2(v);
else if(vis[v]==1)pos=false;
}
vis[u]=2;
}
inline void jump(int &x,int k,int i){
AL2[snode[x][k]].pb(i);
//pf("add: %d %d\n",snode[x][k],i);
AL2[i].pb(tnode[x][k]);
//pf("add: %d %d\n",i,tnode[x][k]);
x=par[x][k];
}
void solve(){
sf("%d",&n);
for(int i=1;i<=n;++i){
AL[i].clear();
sid[i]=tid[i]=-1;
}
for(int i=0;i<n-1;++i){
int a,b;sf("%d%d",&a,&b);
AL[a].pb(b);
AL[b].pb(a);
}
sf("%d",&m);
for(int i=0;i<m;++i){
sf("%d%d",&s[i],&t[i]);
sid[s[i]]=i;
tid[t[i]]=i;
}
cnt=m;
depth[1]=0;dfs(1);
for(int k=1;k<20;++k){
for(int i=1;i<=n;++i){
if(par[i][k-1]!=0){
par[i][k]=par[par[i][k-1]][k-1];
snode[i][k]=cnt++;
tnode[i][k]=cnt++;
AL2[snode[i][k-1]].pb(snode[i][k]);
AL2[snode[par[i][k-1]][k-1]].pb(snode[i][k]);
AL2[tnode[i][k]].pb(tnode[i][k-1]);
AL2[tnode[i][k]].pb(tnode[par[i][k-1]][k-1]);
}
}
}
/*
for(int i=1;i<=n;++i){
pf("%d: ",i);
for(int k=0;k<5;++k){
pf("(%d %d) ",snode[i][k],tnode[i][k]);
}
pf("\n");
}
*/
for(int i=0;i<m;++i){
int a=s[i],b=t[i];
if(depth[a]<depth[b])swap(a,b);
for(int k=19;k>=0;--k){
if(par[a][k]!=0&&depth[par[a][k]]>=depth[b]){
a=par[a][k];
}
}
for(int k=19;k>=0;--k){
if(par[a][k]!=par[b][k]){
a=par[a][k],b=par[b][k];
}
}
int l;
if(a!=b)l=par[a][0];
else l=a;
a=s[i],b=t[i];
if(a!=l){
a=par[a][0];
for(int k=19;k>=0;--k){
if(par[a][k]!=0&&depth[par[a][k]]>=depth[l]){
jump(a,k,i);
}
}
}
if(b!=l){
b=par[b][0];
for(int k=19;k>=0;--k){
if(par[b][k]!=0&&depth[par[b][k]]>=depth[l]){
jump(b,k,i);
}
}
}
if(s[i]!=l&&t[i]!=l){
AL2[snode[l][0]].pb(i);
//pf("add: %d %d\n",snode[l][0],i);
AL2[i].pb(tnode[l][0]);
//pf("add: %d %d\n",i,tnode[l][0]);
}
}
/*
for(int i=0;i<cnt;++i){
disc(AL2[i]);
}
*/
/*
for(int i=0;i<cnt;++i){
for(int j:AL2[i]){
pf("(%d %d) ",i,j);
}
if(AL2[i].size()!=0)pf("\n");
}
*/
for(int i=0;i<cnt;++i){
vis[i]=0;
}
pos=true;
for(int i=0;i<cnt;++i){
if(!vis[i])dfs2(i);
}
if(pos)pf("Yes\n");
else pf("No\n");
for(int i=0;i<cnt;++i)AL2[i].clear();
}
int main(){
int tc;sf("%d",&tc);
while(tc--)solve();
}
Compilation message
jail.cpp: In function 'void solve()':
jail.cpp:108:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | sf("%d",&n);
| ^
jail.cpp:114:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | int a,b;sf("%d%d",&a,&b);
| ^
jail.cpp:118:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
118 | sf("%d",&m);
| ^
jail.cpp:120:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
120 | sf("%d%d",&s[i],&t[i]);
| ^
jail.cpp: In function 'int main()':
jail.cpp:226:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
226 | int tc;sf("%d",&tc);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
144072 KB |
Output is correct |
| 2 |
Incorrect |
73 ms |
143948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
143972 KB |
Output is correct |
| 2 |
Incorrect |
72 ms |
143952 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
143972 KB |
Output is correct |
| 2 |
Incorrect |
72 ms |
143952 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
143972 KB |
Output is correct |
| 2 |
Incorrect |
72 ms |
143952 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
143972 KB |
Output is correct |
| 2 |
Incorrect |
72 ms |
143952 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
144068 KB |
Output is correct |
| 2 |
Runtime error |
950 ms |
949980 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
144072 KB |
Output is correct |
| 2 |
Incorrect |
73 ms |
143948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
