제출 #567242

#제출 시각아이디문제언어결과실행 시간메모리
567242jamielimJail (JOI22_jail)C++14
0 / 100
14 ms9288 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define mp make_pair #define pb emplace_back #define ALL(x) x.begin(),x.end() #define SZ(x) (int)x.size() typedef long long ll; typedef pair<int,int> ii; typedef pair<ii,ii> i4; const int MOD=1000000007; const int INF=1012345678; const ll LLINF=1012345678012345678LL; const double PI=3.1415926536; const double EPS=1e-14; int q,n,m; int fw[120005]; void upd(int x,int y){ y++; while(y<=n){ fw[y]--; y+=y&(-y); } while(x<=n){ fw[x]++; x+=x&(-x); } } int qry(int x){ int res=0; while(x){ res+=fw[x]; x-=x&(-x); } return res; } vector<int> adj[120005]; set<int> dag[120005]; ii arr[120005]; int dep[120005]; int par[20][120005]; void dfs(int x,int p){ par[0][x]=p; for(int i:adj[x]){ if(p==i)continue; dep[i]=dep[x]+1; dfs(i,x); } } int lca(int x,int y){ if(x==y)return x; if(dep[x]>dep[y])swap(x,y); for(int i=19;i>=0;i--){ if(dep[x]<=dep[par[i][y]])y=par[i][y]; } if(x==y)return x; for(int i=19;i>=0;i--){ if(par[i][x]!=par[i][y])x=par[i][x],y=par[i][y]; } return par[0][x]; } int dist(int x,int y){ int l=lca(x,y); int ans=0; for(int i=19;i>=0;i--){ if(dep[par[i][x]]>=dep[l]){ x=par[i][x]; ans+=(1<<i); } } for(int i=19;i>=0;i--){ if(dep[par[i][y]]>=dep[l]){ y=par[i][y]; ans+=(1<<i); } } return ans; } vector<int> topo; int vis[120005]; void toposort(int x){ vis[x]=1; for(int i:dag[x]){ if(vis[i])continue; toposort(i); } topo.pb(x); } int main(){ scanf("%d",&q); while(q--){ scanf("%d",&n); int a,b; bool st1=1; for(int i=1;i<n;i++){ scanf("%d%d",&a,&b); adj[a].pb(b);adj[b].pb(a); if(a!=i||b!=i+1)st1=0; } scanf("%d",&m); for(int i=1;i<=m;i++)scanf("%d%d",&arr[i].fi,&arr[i].se); if(st1){ bool die=0; vector<ii> v1,v2; for(int i=1;i<=m;i++){ if(arr[i].fi<=arr[i].se){ v1.pb(arr[i].fi,arr[i].se); upd(arr[i].fi,arr[i].se); }else{ v2.pb(arr[i].se,arr[i].fi); } } for(int i=1;i<=m;i++){ if(arr[i].fi>arr[i].se){ if(qry(arr[i].se)){ die=1; } } } sort(ALL(v1));sort(ALL(v2)); for(int i=1;i<SZ(v1);i++){ if(v1[i].se<v1[i-1].se)die=1; } for(int i=1;i<SZ(v2);i++){ if(v2[i].se<v2[i-1].se)die=1; } if(die)printf("No\n"); else printf("Yes\n"); for(int i=0;i<=n+2;i++)fw[i]=0; }else{ if(q<=20&&m<=500){ dfs(1,0); dep[0]=-INF; for(int i=1;i<20;i++){ for(int j=1;j<=n;j++){ par[i][j]=par[i-1][par[i-1][j]]; } } int indeg[n+5];memset(indeg,0,sizeof(indeg)); set<int> ctr; for(int i=1;i<=m;i++){ int d=dist(arr[i].fi,arr[i].se); for(int j=1;j<=m;j++){ if(i==j)continue; if(d==dist(arr[i].fi,arr[j].se)+dist(arr[i].se,arr[j].se)){ // j is on path of i => i is before j dag[i].insert(j); indeg[j]++; ctr.insert(i);ctr.insert(j); } } } for(int i=1;i<=n;i++)if(indeg[i]==0)toposort(i); reverse(ALL(topo)); bool die=0; for(int i=1;i<=SZ(topo);i++){ int x=topo[i]; ctr.erase(x); for(int j=i+1;j<=m;j++){ int y=topo[j]; if(dag[y].find(x)!=dag[y].end()){ // y is supposed to be before x die=1; } } } if(die||SZ(ctr)!=0){ printf("No\n"); }else{ printf("Yes\n"); } topo.clear(); memset(vis,0,sizeof(vis)); } } for(int i=1;i<=n;i++)adj[i].clear(); for(int i=1;i<=m;i++)dag[i].clear(); } }

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

jail.cpp: In function 'int main()':
jail.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
jail.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   scanf("%d",&n);
      |   ~~~~~^~~~~~~~~
jail.cpp:107:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |    scanf("%d%d",&a,&b);
      |    ~~~~~^~~~~~~~~~~~~~
jail.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   scanf("%d",&m);
      |   ~~~~~^~~~~~~~~
jail.cpp:112:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   for(int i=1;i<=m;i++)scanf("%d%d",&arr[i].fi,&arr[i].se);
      |                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...