제출 #250414

#제출 시각아이디문제언어결과실행 시간메모리
250414ryansee늑대인간 (IOI18_werewolf)C++14
100 / 100
2864 ms158860 KiB
#include "werewolf.h" #include "bits/stdc++.h" using namespace std; #define FAST ios_base::sync_with_stdio(false); cin.tie(0); #define pb push_back #define eb emplace_back #define ins insert #define f first #define s second #define cbr cerr<<"hi\n" #define mmst(x, v) memset((x), v, sizeof ((x))) #define siz(x) ll(x.size()) #define all(x) (x).begin(), (x).end() #define lbd(x,y) (lower_bound(all(x),y)-x.begin()) #define ubd(x,y) (upper_bound(all(x),y)-x.begin()) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng) inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); } using ll=int; using ld=long double; #define FOR(i,s,e) for(ll i=s;i<=ll(e);++i) #define DEC(i,s,e) for(ll i=s;i>=ll(e);--i) using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; #define LLINF ((long long)1e18) #define INF int(1e9+1e6) #define MAXN (200006) ll n; vector<ll> cost; struct sparse_max { int sp[19][MAXN]; void build(){ FOR(i,0,n-2)sp[0][i]=cost[i]; FOR(h,1,18){ for(ll i=0;i+(1<<h)-1<=n-2;++i){ sp[h][i]=max(sp[h-1][i],sp[h-1][i+(1<<(h-1))]); } } } ll rmq(ll x,ll y){ ll p=__builtin_clz(y-x+1) ^ 31; return max(sp[p][x], sp[p][y-(1<<p)+1]); } } mini; struct sparse_mi { int sp[19][MAXN]; void build(){ FOR(i,0,n-2)sp[0][i]=cost[i]; FOR(h,1,18){ for(ll i=0;i+(1<<h)-1<=n-2;++i){ sp[h][i]=min(sp[h-1][i],sp[h-1][i+(1<<(h-1))]); } } } ll rmq(ll x,ll y){ ll p=__builtin_clz(y-x+1) ^ 31; return min(sp[p][x], sp[p][y-(1<<p)+1]); } } maxi; struct node2 { int s,e,m; vector<ll> v; node2 *l,*r; node2(int S,int E){ s=S,e=E,m=(s+e)>>1; v.clear(); if(s^e)l=new node2(s,m),r=new node2(m+1,e); } void update(int x,ll nval){ if(s==e){ v.eb(nval); return; } if(x>m)r->update(x,nval);else l->update(x,nval); } void prog(){ if(s==e)return; l->prog(), r->prog(); ll co1=0, co2=0; while(co1 < l->v.size() || co2 < r->v.size()){ if(co1 == l->v.size()) { v.eb(r->v[co2++]); continue; } if(co2 == r->v.size()) { v.eb(l->v[co1++]); continue; } if(l->v[co1] <= r->v[co2]) v.eb(l->v[co1++]); else v.eb(r->v[co2++]); } v.resize(unique(all(v))-v.begin()); } bool rmq(int x,int y,int a,int b){ if(s==x&&e==y){ ll ind = lbd(v, a); if(ind == v.size() || v[ind] > b) return 0; return 1; } if(x>m) return r->rmq(x,y,a,b); else if(y<=m) return l->rmq(x,y,a,b); else { if(y - (m+1) >= m - x) { if(!r->rmq(m+1,y,a,b)) return l->rmq(x,m,a,b); return 1; }else{ if(!l->rmq(x,m,a,b)) return r->rmq(m+1,y,a,b); return 1; } } } }*solve; ll q, p[MAXN], pos_mx[MAXN], rope[2][MAXN][2], b, pos_mi[MAXN]; vector<int> ans; vector<pi> v[MAXN], adj[MAXN]; vector<spi> e; bitset<MAXN> vis; int find(int x){return p[x]==x?x:p[x]=find(p[x]);} void merge(int x,int y,ll W){ x=find(x),y=find(y); if(x==y)return; adj[rope[b][x][1]].eb(rope[b][y][0],W); adj[rope[b][y][0]].eb(rope[b][x][1],W); rope[b][y][0]=rope[b][x][0]; p[x]=y; } void build_mx(){ sort(all(e), greater<spi>()); FOR(i,0,n-1)rope[b][i][0]=rope[b][i][1]=i,p[i]=i; for(auto i:e){ merge(i.s.f,i.s.s,i.f); } vector<int> order; function<void(ll,ll)>dfs=[&](ll x,ll p){ if(vis[x])return; vis[x]=1; order.eb(x); for(auto i:adj[x]) if(i.f^p) cost.eb(i.s), dfs(i.f,x); }; vis.reset(), dfs(rope[b][find(0)][0],-1), assert(siz(order)==n), assert(siz(cost)==n-1); FOR(i,0,n-1)pos_mx[order[i]]=i; maxi.build(); } void build_mi(){ b=1; sort(all(e)); FOR(i,0,n-1)rope[b][i][0]=rope[b][i][1]=i,p[i]=i; for(auto i:e){ merge(i.s.f,i.s.s,i.f); } vector<int> order; cost.clear(); function<void(ll,ll)>dfs=[&](ll x,ll p){ if(vis[x])return; vis[x]=1; order.eb(x); for(auto i:adj[x]) if(i.f^p) cost.eb(i.s), dfs(i.f,x); }; vis.reset(), dfs(rope[b][find(0)][0],-1), assert(siz(order)==n), assert(siz(cost)==n-1); FOR(i,0,n-1)pos_mi[order[i]]=i; mini.build(); } vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,std::vector<int> S, std::vector<int> E,std::vector<int> L, std::vector<int> R) { n=N, q=S.size(), ans.resize(q,0); FOR(i,0,siz(X)-1){ v[X[i]].eb(Y[i],min(X[i],Y[i])); v[Y[i]].eb(X[i],min(X[i],Y[i])); e.eb(min(X[i],Y[i]),pi(X[i],Y[i])); } build_mx(); // change edges FOR(i,0,n-1)v[i].clear(),adj[i].clear(); e.clear(); FOR(i,0,siz(X)-1){ v[X[i]].eb(Y[i],max(X[i],Y[i])); v[Y[i]].eb(X[i],max(X[i],Y[i])); e.eb(max(X[i],Y[i]),pi(X[i],Y[i])); } build_mi(); solve=new node2(0,n-1); FOR(i,0,n-1)solve->update(pos_mi[i],pos_mx[i]); solve->prog(); FOR(i,0,q-1){ ll bs[2], be[2]; ll st=-1,en=pos_mx[S[i]]; while(en-st>1){ ll mid=(st+en)>>1; if(maxi.rmq(mid,pos_mx[S[i]]-1)>=L[i])en=mid; else st=mid; } bs[0]=en; st=pos_mx[S[i]],en=n; while(en-st>1){ ll mid=(st+en)>>1; if(maxi.rmq(pos_mx[S[i]],mid-1)>=L[i])st=mid; else en=mid; } bs[1]=st; st=-1,en=pos_mi[E[i]]; while(en-st>1){ ll mid=(st+en)>>1; if(mini.rmq(mid,pos_mi[E[i]]-1)<=R[i])en=mid; else st=mid; } be[0]=en; st=pos_mi[E[i]],en=n; while(en-st>1){ ll mid=(st+en)>>1; if(mini.rmq(pos_mi[E[i]],mid-1)<=R[i])st=mid; else en=mid; } be[1]=st; ans[i] = solve->rmq(be[0],be[1],bs[0],bs[1]); } return ans; }

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

werewolf.cpp: In member function 'void node2::prog()':
werewolf.cpp:83:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(co1 < l->v.size() || co2 < r->v.size()){
         ~~~~^~~~~~~~~~~~~
werewolf.cpp:83:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(co1 < l->v.size() || co2 < r->v.size()){
                              ~~~~^~~~~~~~~~~~~
werewolf.cpp:84:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(co1 == l->v.size()) { v.eb(r->v[co2++]); continue; }
       ~~~~^~~~~~~~~~~~~~
werewolf.cpp:85:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(co2 == r->v.size()) { v.eb(l->v[co1++]); continue; }
       ~~~~^~~~~~~~~~~~~~
werewolf.cpp: In member function 'bool node2::rmq(int, int, int, int)':
werewolf.cpp:94:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ind == v.size() || v[ind] > b) return 0;
       ~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...