Submission #288144

#	Time	Username	Problem	Language	Result	Execution time	Memory
288144		Noam13	Werewolf (IOI18_werewolf)	C++14	100 / 100	1644 ms	191840 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vi>
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
#define pb push_back
#define ii pair<int, int>
#define vii vector<ii>
#define vvii vector<vii>
#define x first
#define y second
#define all(a) a.begin(),a.end()
#define chkmax(a,b) a = max(a,b)
#define chkmin(a,b) a = min(a,b)
using namespace std;


struct DSU{
	int n;
	vi p, sz;
	DSU(int n=0): n(n), p(n,-1), sz(n,1){}
	void init(int nn){
		n = nn;
		p.clear(); sz.clear(); 
		p.resize(n,-1); sz.resize(n,1);
	}
	int find(int c){
		if (p[c]==-1) return c;
		return p[c] = find(p[c]);
	}
	bool uni(int a, int b){
		a = find(a), b = find(b);
		if (a==b) return 0;
		//if (sz[a]>sz[b]) swap(a,b);
		p[a] = b;
		sz[b] += sz[a];
		return 1;
	}
};
const int INF = 1e9;
struct BINARY{
	int n, log;
	vvii g;
	vvi anc, mine;
	vi order, pos;
	vi in, out;
	int t = 0;
	BINARY(vvii& _g, int s=0): g(_g), n(_g.size()){
		for(log=1; (1<<log)<n;log++);
		anc.resize(n, vi(log, -1));
		mine.resize(n, vi(log, -INF));
		in.resize(n); out.resize(n);
		dfs(s);
		pos.resize(n);
		loop(i,0,n) pos[order[i]] = i;
	}
	void dfs(int cur, int p=-1, int pw=-INF){
		order.pb(cur); in[cur] = t++;
		anc[cur][0] = p; mine[cur][0] = pw;
		loop(i,1,log){
			if (anc[cur][i-1]==-1) break;
			anc[cur][i] = anc[anc[cur][i-1]][i-1];
			mine[cur][i] = min(mine[cur][i-1], mine[anc[cur][i-1]][i-1]);
		}
		for(auto nei:g[cur]) if(nei.x!=p){
			dfs(nei.x, cur, nei.y);
		}
		out[cur] = t-1;
	}
	int lift(int cur, int L){
		loopr(i,0,log){
			if (mine[cur][i]>=L){
				cur = anc[cur][i];
			}
		}
		return cur;
	}
};
struct Qur{
	int x, l, r;
	int ind; bool in;
	bool operator<(const Qur& a){
		return x < a.x;
	}
};
struct SEG{
	int sz;
	vi a;
	SEG(int n){
		for(sz=1;sz<n;sz*=2);
		a.resize(2*sz);
	}
	void update(int i, int x){
		a[i+=sz]=x;
		for(i/=2;i;i/=2) a[i] = a[2*i] + a[2*i+1];
	}
	int query(int l, int r){
		int ans =  0;
		for(l+=sz, r+=sz; l<=r; l/=2, r/=2){
			if (l%2) ans+=a[l++];
			if (r%2==0) ans+=a[r--];
		}
		return ans;
	}
};
vi check_validity(int N, vi u, vi v, vi S, vi E, vi L, vi R) {
	int n = N, m = u.size(), q=S.size();
	
	vvi g(n);
	loop(i,0,m){
		int a = u[i], b = v[i];
		g[a].pb(b);
		g[b].pb(a);
	}
	vector<ii> mine, maxe;
	DSU dsu(n);
	loopr(i,0,n){
		for(auto j:g[i]){
			if (j<i) continue;
			int x = dsu.find(j);
			if (x!=i){
				mine.pb({x,i});
				dsu.p[x] = i;
			} 
		}
	}
	dsu.init(n);
	loop(i,0,n){
		for(auto j:g[i]){
			if (j>i) continue;
			int x = dsu.find(j);
			if (x!=i){
				maxe.pb({x,i});
				dsu.p[x] = i;
			} 
		}
	}
	vvii gs(n), ge(n);
	for(auto e:mine){
		gs[e.x].pb({e.y, min(e.x, e.y)});
		gs[e.y].pb({e.x, min(e.x, e.y)});
	}
	for(auto e:maxe){
		//cout<<e.x<<" "<<e.y<<endl;
		ge[e.x].pb({e.y, -max(e.x, e.y)});
		ge[e.y].pb({e.x, -max(e.x, e.y)});
	}
	BINARY bins(gs, 0), bine(ge, n-1);
	//loop(i,0,n) cout<<bine.order[i]<<" "; cout<<endl;
	vector<Qur> eve;
	loop(i,0,q){
		int a = bins.lift(S[i], L[i]), b = bine.lift(E[i], -R[i]);
		eve.pb({bins.in[a]-1, bine.in[b], bine.out[b], i, 1});
		eve.pb({bins.out[a], bine.in[b], bine.out[b], i, 0});
		//cout<<"AB: "<<a<<" "<<b<<endl;
		//cout<<bine.in[b]<< " " << bine.out[b] << endl;
		//cout<<bins.in[a]<< " " << bins.out[a] << endl;
	}
	sort(all(eve));
	SEG seg(n);
	vi ans(q); int ind = 0;
	for(auto &e:eve){
		while(ind<=e.x){
			seg.update(bine.pos[bins.order[ind]], 1);
			ind++;
		}
		int v = seg.query(e.l, e.r);
		//cout<<"V: "<<v<<endl;
		ans[e.ind]+=(e.in?-v:v);
	}
	loop(i,0,q) if(ans[i]>0) ans[i]=1;
	return ans;
}
/*
clear
g++ werewolf.cpp grader.cpp -o a ; ./a
10 9 1
6 7
1 5
8 0
2 9
9 4
2 7
8 5
6 0
3 4
8 9 3 9
*/

Compilation message (stderr)

werewolf.cpp: In constructor 'BINARY::BINARY(std::vector<std::vector<std::pair<int, int> > >&, int)':
werewolf.cpp:44:7: warning: 'BINARY::g' will be initialized after [-Wreorder]
   44 |  vvii g;
      |       ^
werewolf.cpp:43:6: warning:   'int BINARY::n' [-Wreorder]
   43 |  int n, log;
      |      ^
werewolf.cpp:49:2: warning:   when initialized here [-Wreorder]
   49 |  BINARY(vvii& _g, int s=0): g(_g), n(_g.size()){
      |  ^~~~~~

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