제출 #567188

#제출 시각아이디문제언어결과실행 시간메모리
567188tqbfjotldJail (JOI22_jail)C++14
0 / 100
27 ms19672 KiB
#include <bits/stdc++.h> using namespace std; vector<int> adjl[120005]; int vis[400005]; int cur; int fs[120005]; int ls[120005]; int A[120005]; int B[120005]; vector<int> adjl2[400005]; int curid = 0; struct node{ int s,e,inid,outid; node *l,*r; vector<int> stuff; node (int _s, int _e){ s = _s; e = _e; inid = curid++; outid = curid++; if (s!=e){ l = new node(s,(s+e)/2); r = new node((s+e)/2+1,e); } } void add(int a, int b, int val){ if (a<=s && e<=b){ stuff.push_back(val); return; } if (b<=(s+e)/2) l->add(a,b,val); else if (a>(s+e)/2) r->add(a,b,val); else { l->add(a,b,val); r->add(a,b,val); } } void constructstuff(){ if (s!=e){ l->constructstuff(); r->constructstuff(); } for (auto y : stuff){ adjl2[inid].push_back(y); adjl2[y].push_back(outid); } } void constructbef(int pos, int val){ adjl2[val].push_back(inid); if (s==e) return; if (pos<=(s+e)/2) l->constructbef(pos,val); else r->constructbef(pos,val); } void constructaft(int pos, int val){ adjl2[outid].push_back(val); if (s==e) return; if (pos<=(s+e)/2) l->constructaft(pos,val); else r->constructaft(pos,val); } }*root; int p[120005]; int hd[120005]; int dep[120005]; int sz[120005]; int pre[120005]; int ct = 0; void dfs(int nd){ sz[nd] = 1; for (auto x : adjl[nd]){ if (x==p[nd]){ continue; } dep[x] = dep[nd]+1; p[x] = nd; dfs(x); sz[nd] += sz[x]; } } void decomp(int nd, int head){ hd[nd] = head; pre[nd] = ct++; int mx = 0; int mnd = -1; for (auto x : adjl[nd]){ if (x==p[nd]) continue; if (sz[x]>mx){ mx = sz[x]; mnd = x; } } if (mnd==-1) return; decomp(mnd,head); for (auto x : adjl[nd]){ if (x==p[nd]||x==mnd) continue; decomp(x,x); } } bool checkcycle(int nd){ if (vis[nd]==2) return false; vis[nd] = 1; for (auto x : adjl2[nd]){ if (vis[x]==1) return true; if (checkcycle(x)) return true; } vis[nd] = 2; return false; } int p2[120005][20]; int anc(int a, int amt){ for (int x = 0; x<20; x++){ if ((1<<x)&amt){ a = p2[a][x]; } } return a; } int main(){ int Q; scanf("%d",&Q); while (Q--){ int n; scanf("%d",&n); ct = 0; for (int x = 1; x<=n; x++){ adjl[x].clear(); } for (int x = 0; x<n-1; x++){ int a,b; scanf("%d%d",&a,&b); adjl[a].push_back(b); adjl[b].push_back(a); } p[1] = 0; dfs(1); decomp(1,1); for (int x = 0; x<=n; x++){ p2[x][0] = p[x]; } for (int x = 1; x<20; x++){ for (int y = 0; y<=n; y++){ p2[y][x] = p2[p2[y][x-1]][x-1]; } } int m; scanf("%d",&m); curid = m; for (int x = 1; x<=n; x++){ fs[x] = -1; ls[x] = -1; } for (int x = 0; x<m; x++){ scanf("%d%d",&A[x],&B[x]); fs[A[x]] = x; ls[B[x]] = x; } root = new node(0,n-1); for (int x = 0; x<m; x++){ int a = A[x]; int b = B[x]; if (dep[a]>dep[b]) swap(a,b); if (p[b]==a) continue; if (anc(b,dep[b]-dep[a])==a){ a = anc(b,dep[b]-dep[a]-1); b = p[b]; } else{ a = p[a]; b = p[b]; } while (hd[a]!=hd[b]){ if (dep[hd[a]]<dep[hd[b]]) swap(a,b); root->add(pre[hd[a]],pre[a],x); a = p[hd[a]]; } if (pre[a]>pre[b])swap(a,b); root->add(pre[a],pre[b],x); } for (int x = 0; x<3*n+5; x++){ adjl2[x].clear(); vis[x] = 0; } root->constructstuff(); for (int x = 1; x<=n; x++){ if (fs[x]!=-1 && ls[x]!=-1) adjl2[fs[x]].push_back(ls[x]); if (fs[x]!=-1){ root->constructbef(pre[x],fs[x]); } if (ls[x]!=-1){ root->constructaft(pre[x],ls[x]); } } bool ans = true; for (int x = 0; x<curid; x++){ if (checkcycle(x)){ ans = false; } } printf(ans?"Yes\n":"No\n"); } }

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

jail.cpp: In function 'int main()':
jail.cpp:132:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
jail.cpp:135:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
jail.cpp:142:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |             scanf("%d%d",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~
jail.cpp:160:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         scanf("%d",&m);
      |         ~~~~~^~~~~~~~~
jail.cpp:167:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |             scanf("%d%d",&A[x],&B[x]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~
#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...