oj.uz

Submission #250414

# Submission time Handle Problem Language Result Execution time Memory
250414 2020-07-17T19:13:16 Z ryansee Werewolf (IOI18_werewolf) C++14
100 / 100
 2864 ms 158860 KB 
#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;
}

Compilation message

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9856 KB Output is correct
2 Correct 6 ms 9856 KB Output is correct
3 Correct 6 ms 9856 KB Output is correct
4 Correct 6 ms 9856 KB Output is correct
5 Correct 6 ms 9856 KB Output is correct
6 Correct 7 ms 9856 KB Output is correct
7 Correct 6 ms 9856 KB Output is correct
8 Correct 6 ms 9856 KB Output is correct
9 Correct 6 ms 9856 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9856 KB Output is correct
2 Correct 6 ms 9856 KB Output is correct
3 Correct 6 ms 9856 KB Output is correct
4 Correct 6 ms 9856 KB Output is correct
5 Correct 6 ms 9856 KB Output is correct
6 Correct 7 ms 9856 KB Output is correct
7 Correct 6 ms 9856 KB Output is correct
8 Correct 6 ms 9856 KB Output is correct
9 Correct 6 ms 9856 KB Output is correct
10 Correct 15 ms 11776 KB Output is correct
11 Correct 16 ms 11776 KB Output is correct
12 Correct 16 ms 11776 KB Output is correct
13 Correct 16 ms 11776 KB Output is correct
14 Correct 16 ms 11776 KB Output is correct
15 Correct 17 ms 11904 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2705 ms 145084 KB Output is correct
2 Correct 1364 ms 145172 KB Output is correct
3 Correct 1376 ms 145060 KB Output is correct
4 Correct 1913 ms 144956 KB Output is correct
5 Correct 1889 ms 144948 KB Output is correct
6 Correct 2641 ms 145176 KB Output is correct
7 Correct 1757 ms 144932 KB Output is correct
8 Correct 1205 ms 145008 KB Output is correct
9 Correct 936 ms 144952 KB Output is correct
10 Correct 932 ms 145064 KB Output is correct
11 Correct 1085 ms 144960 KB Output is correct
12 Correct 1111 ms 144956 KB Output is correct
13 Correct 2222 ms 144964 KB Output is correct
14 Correct 2001 ms 144948 KB Output is correct
15 Correct 1659 ms 144956 KB Output is correct
16 Correct 2073 ms 145028 KB Output is correct
17 Correct 2039 ms 144948 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9856 KB Output is correct
2 Correct 6 ms 9856 KB Output is correct
3 Correct 6 ms 9856 KB Output is correct
4 Correct 6 ms 9856 KB Output is correct
5 Correct 6 ms 9856 KB Output is correct
6 Correct 7 ms 9856 KB Output is correct
7 Correct 6 ms 9856 KB Output is correct
8 Correct 6 ms 9856 KB Output is correct
9 Correct 6 ms 9856 KB Output is correct
10 Correct 15 ms 11776 KB Output is correct
11 Correct 16 ms 11776 KB Output is correct
12 Correct 16 ms 11776 KB Output is correct
13 Correct 16 ms 11776 KB Output is correct
14 Correct 16 ms 11776 KB Output is correct
15 Correct 17 ms 11904 KB Output is correct
16 Correct 2705 ms 145084 KB Output is correct
17 Correct 1364 ms 145172 KB Output is correct
18 Correct 1376 ms 145060 KB Output is correct
19 Correct 1913 ms 144956 KB Output is correct
20 Correct 1889 ms 144948 KB Output is correct
21 Correct 2641 ms 145176 KB Output is correct
22 Correct 1757 ms 144932 KB Output is correct
23 Correct 1205 ms 145008 KB Output is correct
24 Correct 936 ms 144952 KB Output is correct
25 Correct 932 ms 145064 KB Output is correct
26 Correct 1085 ms 144960 KB Output is correct
27 Correct 1111 ms 144956 KB Output is correct
28 Correct 2222 ms 144964 KB Output is correct
29 Correct 2001 ms 144948 KB Output is correct
30 Correct 1659 ms 144956 KB Output is correct
31 Correct 2073 ms 145028 KB Output is correct
32 Correct 2039 ms 144948 KB Output is correct
33 Correct 2864 ms 146088 KB Output is correct
34 Correct 560 ms 53020 KB Output is correct
35 Correct 2160 ms 147260 KB Output is correct
36 Correct 2614 ms 145360 KB Output is correct
37 Correct 2255 ms 146644 KB Output is correct
38 Correct 2358 ms 145708 KB Output is correct
39 Correct 2632 ms 146256 KB Output is correct
40 Correct 1998 ms 158860 KB Output is correct
41 Correct 1545 ms 146484 KB Output is correct
42 Correct 1210 ms 145368 KB Output is correct
43 Correct 1682 ms 152020 KB Output is correct
44 Correct 2176 ms 146692 KB Output is correct
45 Correct 1039 ms 146780 KB Output is correct
46 Correct 1016 ms 146216 KB Output is correct
47 Correct 1958 ms 145348 KB Output is correct
48 Correct 2173 ms 144928 KB Output is correct
49 Correct 1837 ms 145356 KB Output is correct
50 Correct 1998 ms 145016 KB Output is correct
51 Correct 1751 ms 158596 KB Output is correct
52 Correct 1856 ms 158724 KB Output is correct