제출 #250414

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
250414		ryansee	늑대인간 (IOI18_werewolf)	C++14	100 / 100	2864 ms	158860 KiB

werewolf

#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;
       ~~~~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51