제출 #718755

#제출 시각아이디문제언어결과실행 시간메모리
718755ogibogi2004Werewolf (IOI18_werewolf)C++14
0 / 100
1294 ms366184 KiB
#include "werewolf.h" #include<bits/stdc++.h> using namespace std; const int MAXN=4e5+6; const int logN=18; struct node { int left_child,right_child,maxval; }; vector<node>nodes; vector<int>g[MAXN]; int in_time[MAXN][2]; int out_time[MAXN][2]; int par[2][MAXN][logN]; int x[MAXN],y[MAXN]; struct tree_2d { set<int>s[3*MAXN]; void build(int l,int r,int idx) { for(int i=l;i<=r;i++)s[idx].insert(y[i]); if(l==r)return; int mid=(l+r)/2; build(l,mid,idx*2); build(mid+1,r,idx*2+1); } bool query(int l,int r,int idx,int ql,int qr,int ql1,int qr1) { if(l>qr)return 0; if(r<ql)return 0; if(l>=ql&&r<=qr) { auto it=s[idx].lower_bound(ql1); if(it!=s[idx].end()&&(*it)<=qr1)return 1; return 0; } int mid=(l+r)/2; return query(l,mid,idx*2,ql,qr,ql1,qr1)||query(mid+1,r,idx*2+1,ql,qr,ql1,qr1); } }tr; struct dsu { int par[2*MAXN]; void init() { for(int i=0;i<MAXN;i++) { par[i]=i; } } int getRoot(int u) { if(u==par[u])return u; return par[u]=getRoot(par[u]); } void join(int p,int q,int f) { p=getRoot(p); q=getRoot(q); if(p==q)return; int t=nodes.size(); par[p]=t;par[q]=t; if(!f)nodes.push_back({p,q,max(nodes[p].maxval,nodes[q].maxval)}); else nodes.push_back({p,q,min(nodes[p].maxval,nodes[q].maxval)}); } }dsu1; int t,n; void dfs(int u,int p,int f) { in_time[u][f]=++t; par[f][u][0]=p; if(nodes[u].left_child!=-1)dfs(nodes[u].left_child,u,f); if(nodes[u].right_child!=-1)dfs(nodes[u].right_child,u,f); out_time[u][f]=t; } void precompute() { for(int f=0;f<1;f++) for(int step=1;step<logN;step++) { for(int i=0;i<n;i++) { if(par[f][i][step-1]==-1)par[f][i][step]=-1; else par[f][i][step]=par[f][par[f][i][step-1]][step-1]; } } } int lift_left(int vert,int l) { if(vert<l)return -1; for(int j=logN-1;j>=0;j--) { if(par[0][vert][j]==-1)continue; if(nodes[par[0][vert][j]].maxval<l)continue; vert=par[0][vert][j]; } return vert; } int lift_right(int vert,int r) { if(vert>r)return -1; for(int j=logN-1;j>=0;j--) { if(par[1][vert][j]==-1)continue; if(nodes[par[1][vert][j]].maxval>r)continue; vert=par[1][vert][j]; } return vert; } vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) { n=N; for(int i=0;i<X.size();i++) { g[X[i]].push_back(Y[i]); g[Y[i]].push_back(X[i]); } for(int i=0;i<N;i++) { nodes.push_back({-1,-1,i}); } //cout<<"*0\n"; dsu1.init(); for(int i=N-1;i>=0;i--) { //cout<<"%% "<<i<<endl; for(auto xd:g[i]) { if(xd>i) { dsu1.join(xd,i,0); } } } t=0; //cout<<"*0.5\n"; dfs(nodes.size()-1,-1,0); //cout<<"*1\n"; nodes.clear(); for(int i=0;i<N;i++) { nodes.push_back({-1,-1,i}); } dsu1.init(); for(int i=0;i<N;i++) { for(auto xd:g[i]) { if(xd<i) { dsu1.join(xd,i,1); } } } t=0; dfs(nodes.size()-1,-1,1); precompute(); //cout<<"*2\n"; for(int i=0;i<N;i++) { x[i]=in_time[i][0]; y[i]=in_time[i][1]; //cout<<x[i]<<" "<<y[i]<<endl; } tr.build(1,nodes.size(),1); vector<int>ans; //cout<<"*3\n"; for(int i=0;i<L.size();i++) { int t1=lift_left(S[i],L[i]); int t2=lift_right(E[i],R[i]); if(t1!=-1&&t2!=-1&&tr.query(1,nodes.size(),1,in_time[t1][0], out_time[t1][0],in_time[t2][1],out_time[t2][1])) { ans.push_back(1); } else ans.push_back(0); } return ans; }

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

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:116:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for(int i=0;i<X.size();i++)
      |                     ~^~~~~~~~~
werewolf.cpp:173:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |         for(int i=0;i<L.size();i++)
      |                     ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...