제출 #570103

#제출 시각아이디문제언어결과실행 시간메모리
570103jamezzzJail (JOI22_jail)C++17
0 / 100
118 ms256800 KiB
#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; vector<int> svec[maxn][20],tvec[maxn][20]; vi AL[maxn],AL2[maxn*50]; int vis[maxn*50]; bool pos=false; void dfs(int u){ for(int v:AL[u]){ if(v==par[u][0])continue; par[v][0]=u; depth[v]=depth[u]+1; snode[v][0]=cnt++; tnode[v][0]=cnt++; if(sid[u]!=-1)svec[v][0].pb(sid[u]); if(tid[u]!=-1)tvec[v][0].pb(tid[u]); 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){ //pf("jump: %d %d %d\n",x,k,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 k=0;k<20;++k){ svec[i][k].clear(); tvec[i][k].clear(); } } 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++; for(int x:svec[i][k-1])svec[i][k].pb(x); for(int x:tvec[i][k-1])tvec[i][k].pb(x); for(int x:svec[par[i][k-1]][k-1])svec[i][k].pb(x); for(int x:tvec[par[i][k-1]][k-1])tvec[i][k].pb(x); } } } for(int i=0;i<cnt;++i){ AL2[i].clear(); } /* for(int i=1;i<=n;++i){ for(int k=0;k<5;++k){ if(!svec[i][k].empty()){ pf("svec[%d][%d]: ",i,k); for(int x:svec[i][k])pf("%d ",x); pf("\n"); } if(!tvec[i][k].empty()){ pf("tvec[%d][%d]: ",i,k); for(int x:tvec[i][k])pf("%d ",x); pf("\n"); } } } 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 k=0;k<20;++k){ for(int i=1;i<=n;++i){ for(int x:svec[i][k])AL2[x].pb(snode[i][k]);//,pf("add0: %d %d\n",x,snode[i][k]); for(int x:tvec[i][k])AL2[tnode[i][k]].pb(x);//,pf("add0: %d %d\n",tnode[i][k],x); } } 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]){ jump(a,k,i); } } if(par[a][0]==b)continue; for(int k=19;k>=0;--k){ if(par[a][k]!=par[b][k]){ jump(a,k,i); jump(b,k,i); } } if(sid[a]!=-1&&tid[a]!=-1){ AL2[sid[a]].pb(tid[a]); } } 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"); } int main(){ int tc;sf("%d",&tc); while(tc--)solve(); }

컴파일 시 표준 에러 (stderr) 메시지

jail.cpp: In function 'void solve()':
jail.cpp:98:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |  sf("%d",&n);
      |    ^
jail.cpp:108:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |   int a,b;sf("%d%d",&a,&b);
      |             ^
jail.cpp:112:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |  sf("%d",&m);
      |    ^
jail.cpp:114:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |   sf("%d%d",&s[i],&t[i]);
      |     ^
jail.cpp: In function 'int main()':
jail.cpp:220:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  220 |  int tc;sf("%d",&tc);
      |           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...