oj.uz

Submission #376646

# Submission time Handle Problem Language Result Execution time Memory
376646 2021-03-11T23:13:55 Z Gajowy Werewolf (IOI18_werewolf) C++14
100 / 100
 1241 ms 154148 KB 
/*
Antoni Dlugosz
VLO Krakow

"You know google - they ask you interview questions, well, the kind of question i face on the job is: 
"is this bad, is this too much voodoo for our purposes for our mission statement?". 
Our mission is to be a modern Commodore64, is this too much voodoo that, this is the op-, this, 
there is, this is voodoo, the question is "is this too much?" and that's, this is the hardest question 
you could ever face in programming.  This right here is the hardest question, right here, right here is the 
hardest question in programming, "is this too much voodoo for the next ten centuries?", as f-, for god's officlal temple, 
Holy, Holy C is the hardest question in programming, right here, okay, there it is, the hardest question in programming." 
 ~ the late Terry A. Davis
*/

//fast stuff
//#pragma GCC optimize("Ofast")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define mp        make_pair
#define eb        emplace_back
#define pb        push_back
#define e1        first
#define e2        second
#define vt        vector
#define size(x)   (int32_t)x.size()
#define all(r)    begin(r),end(r)
#define fastio    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define time      chrono::high_resolution_clock().now().time_since_epoch().count()
#define satori    int32_t TCS; cin>>TCS; while(TCS--)
#ifndef DEBUGMODE
#define DEBUGMODE false
#endif
#define debug     if(DEBUGMODE)

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int uint;
	
template<typename T>
using ordset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

struct reachability_tree{
	int n;
	struct node{
		int sz,fusz,rep,order,mx,trueorder,time_added;
		vt<int> sons;
	};
	vt<node> nodes;
	vt<vt<pair<int,int>>> e;
	int fnd(int p){
		return (nodes[p].rep==p?p:nodes[p].rep=fnd(nodes[p].rep));
	}
	bool dif(int u,int v){
		u=fnd(u);
		v=fnd(v);
		return (u!=v);
	}
	void onion(int u,int v){
		u=fnd(u);
		v=fnd(v);
		if(u==v)
			return;
		if(nodes[u].fusz<nodes[v].fusz)
			swap(u,v);
		nodes[u].fusz+=nodes[v].fusz;
		nodes[v].rep=u;
		nodes[u].mx=max(nodes[u].mx,nodes[v].mx);
	}
	void prep(){
		for(int i=0;i<n;i++)
			nodes.pb({1,1,i,0,i,0,-1,{}});
		for(int i=0;i<n;i++){
			for(auto edge:e[i]){
				int u=edge.e1;
				int v=edge.e2;
				if(dif(u,v)){
					int par_u=nodes[fnd(u)].mx;
					int par_v=nodes[fnd(v)].mx;
					int new_par_id=size(nodes);
					nodes.pb({0,1,new_par_id,0,new_par_id,0,i,{}});
					onion(par_u,new_par_id);
					onion(par_v,new_par_id);
					nodes[new_par_id].sons.eb(par_u);
					nodes[new_par_id].sons.eb(par_v);
				}
			}
		}
		int lorder=-1;
		int	ltrueorder=-1;
		function<void(int)> dfs=[&](int u){
			nodes[u].order=n;
			if(u<n){
				lorder++;
				nodes[u].order=lorder;
			}
			ltrueorder++;
			nodes[u].trueorder=ltrueorder;
			for(auto v:nodes[u].sons)
				dfs(v),nodes[u].sz+=nodes[v].sz,nodes[u].order=min(nodes[u].order,nodes[v].order);
		};
		dfs(size(nodes)-1);
	}
	reachability_tree(int N,vt<vt<pair<int,int>>> &E){
		n=N;
		swap(e,E);
		prep();
	}
	void get_ids(vt<int> &ids){
		ids.resize(n);
		for(int i=0;i<n;i++)
			ids[i]=nodes[i].order;
	}
	void get_ranges(vt<int> &id,vt<int> &tim,vt<int> &resl,vt<int> &resr){
		int q=size(id);
		resl.resize(q,0);
		resr.resize(q,0);
		vt<vt<int>> qrs(n);
		for(int i=0;i<q;i++)
			qrs[id[i]].eb(i);
		vt<int> anc;
		function<void(int)> dfs=[&](int u){
			anc.eb(u);
			if(u<n){
				for(auto idd:qrs[u]){
					int l=0,r=size(anc)-1;
					int bspos=-1;
					while(l<=r){
						int md=(l+r)/2;
						if(nodes[anc[md]].time_added<=tim[idd])
							bspos=md,r=md-1;
						else
							l=md+1;
					}
					resl[idd]=nodes[anc[bspos]].order;
					resr[idd]=nodes[anc[bspos]].sz+resl[idd]-1;
				}
			}
			for(auto v:nodes[u].sons)
				dfs(v);
			anc.pop_back();
		};
		dfs(size(nodes)-1);
	}
};

struct fenwick_tree{
	vt<int> v;
	int n;
	fenwick_tree(int N=0){
		n=N;
		v.resize(n+2,0);
	}
	void add(int pos){
		pos++;
		for(;pos<=n+1;pos=(pos|(pos-1))+1)
			v[pos]++;
	}
	int leq(int pos){
		pos++;
		int ans=0;
		for(;pos;pos=(pos&(pos-1)))
			ans+=v[pos];
		return ans;
	}
};

struct sweepline_checker{
	vt<int> recres;
	struct point{
		int x,y,recid,sgn;
	};
	vt<point> points;
	fenwick_tree ft;
	sweepline_checker(vt<int> &ptx,vt<int> &pty,vt<int> &recxmn,vt<int> &recxmx,vt<int> &recymn,vt<int> &recymx){
		recres.resize(size(recxmn),0);
		int mx_y_coord=0;
		for(int i=0;i<size(ptx);i++)
			points.pb({ptx[i],pty[i],-1,0}),mx_y_coord=max(mx_y_coord,pty[i]);
		for(int i=0;i<size(recxmn);i++){
			points.pb({recxmx[i],recymx[i],i,1});
			if(recxmn[i]-1>=0&&recymn[i]-1>=0)
				points.pb({recxmn[i]-1,recymn[i]-1,i,1});
			if(recymn[i]-1>=0)
				points.pb({recxmx[i],recymn[i]-1,i,-1});
			if(recxmn[i]-1>=0)
				points.pb({recxmn[i]-1,recymx[i],i,-1});
			mx_y_coord=max(mx_y_coord,recymx[i]);
		}
		ft=fenwick_tree(mx_y_coord);
	}
	static bool cmp(point &a,point &b){
		return (a.x==b.x?(a.y==b.y?(a.recid<b.recid):(a.y<b.y)):a.x<b.x);
	}
	void solve_sweepline(vt<int> &res){
		sort(all(points),cmp);
		for(auto &pt:points){
			if(pt.recid!=-1){
				int counted_points=ft.leq(pt.y)*pt.sgn;
				recres[pt.recid]+=counted_points;
			}
			else
				ft.add(pt.y);
		}
		swap(res,recres);
	}
};

vt<int> check_validity(int n,vt<int> X,vt<int> Y, vt<int> mxbegin,vt<int> mnbegin,vt<int> mxrange,vt<int> mnrange){
	int m=size(X);
	int q=size(mxbegin);
	vt<vt<pair<int,int>>> mne(n);
	vt<vt<pair<int,int>>> mxe(n);
	for(int i=0;i<m;i++){
		int mn=max(X[i],Y[i]);
		int mx=n-min(X[i],Y[i])-1;
		mne[mn].pb({X[i],Y[i]});
		mxe[mx].pb({X[i],Y[i]});
	}
	for(int i=0;i<q;i++)
		mxrange[i]=n-mxrange[i]-1;
	reachability_tree mnt(n,mne);
	reachability_tree mxt(n,mxe);
	vt<int> mnid,mxid;
	mnt.get_ids(mnid);
	mxt.get_ids(mxid);
	vt<int> qlmn,qrmn,qlmx,qrmx;
	mnt.get_ranges(mnbegin,mnrange,qlmn,qrmn);
	mxt.get_ranges(mxbegin,mxrange,qlmx,qrmx);
	sweepline_checker slc(mnid,mxid,qlmn,qrmn,qlmx,qrmx);
	vt<int> res;
	slc.solve_sweepline(res);
	for(int i=0;i<q;i++)
		res[i]=min(res[i],1);
	return res;
}

/*
stuff declared locally is not always equal to zero!
pointers on 64-bit environments take up 64 bits, not 32
vectors take up a lot of space
bitsets don't take up a lot of space
going out of bounds is bad
too much voodoo is bad
too much abstraction doesn't really impact performance in c++
abstraction is good
not returning in a non void function is bad
infinite loops are bad
overflow is bad
declaring stuff locally is good
cc_hash_table has faster queries, but considerably slower updates than gp_hash_table
overanalyzing stuff is good
assume nothing works correctly
don't do dumb stuff
speedrun writing slow solutions and generators at the start of the contest
remember to use pragmas :)
*/

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 10 ms 2444 KB Output is correct
11 Correct 10 ms 2464 KB Output is correct
12 Correct 10 ms 2316 KB Output is correct
13 Correct 10 ms 2596 KB Output is correct
14 Correct 10 ms 2592 KB Output is correct
15 Correct 11 ms 2448 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1186 ms 123888 KB Output is correct
2 Correct 1065 ms 141600 KB Output is correct
3 Correct 1004 ms 135584 KB Output is correct
4 Correct 1014 ms 132784 KB Output is correct
5 Correct 1018 ms 134296 KB Output is correct
6 Correct 1168 ms 133952 KB Output is correct
7 Correct 1135 ms 131452 KB Output is correct
8 Correct 897 ms 139968 KB Output is correct
9 Correct 857 ms 131708 KB Output is correct
10 Correct 842 ms 130748 KB Output is correct
11 Correct 878 ms 132248 KB Output is correct
12 Correct 964 ms 130620 KB Output is correct
13 Correct 1126 ms 145628 KB Output is correct
14 Correct 1165 ms 147372 KB Output is correct
15 Correct 1115 ms 147356 KB Output is correct
16 Correct 1122 ms 147460 KB Output is correct
17 Correct 1133 ms 130988 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 10 ms 2444 KB Output is correct
11 Correct 10 ms 2464 KB Output is correct
12 Correct 10 ms 2316 KB Output is correct
13 Correct 10 ms 2596 KB Output is correct
14 Correct 10 ms 2592 KB Output is correct
15 Correct 11 ms 2448 KB Output is correct
16 Correct 1186 ms 123888 KB Output is correct
17 Correct 1065 ms 141600 KB Output is correct
18 Correct 1004 ms 135584 KB Output is correct
19 Correct 1014 ms 132784 KB Output is correct
20 Correct 1018 ms 134296 KB Output is correct
21 Correct 1168 ms 133952 KB Output is correct
22 Correct 1135 ms 131452 KB Output is correct
23 Correct 897 ms 139968 KB Output is correct
24 Correct 857 ms 131708 KB Output is correct
25 Correct 842 ms 130748 KB Output is correct
26 Correct 878 ms 132248 KB Output is correct
27 Correct 964 ms 130620 KB Output is correct
28 Correct 1126 ms 145628 KB Output is correct
29 Correct 1165 ms 147372 KB Output is correct
30 Correct 1115 ms 147356 KB Output is correct
31 Correct 1122 ms 147460 KB Output is correct
32 Correct 1133 ms 130988 KB Output is correct
33 Correct 1180 ms 136432 KB Output is correct
34 Correct 491 ms 55720 KB Output is correct
35 Correct 1195 ms 141116 KB Output is correct
36 Correct 1177 ms 133844 KB Output is correct
37 Correct 1188 ms 140956 KB Output is correct
38 Correct 1184 ms 136684 KB Output is correct
39 Correct 1114 ms 154148 KB Output is correct
40 Correct 1233 ms 147368 KB Output is correct
41 Correct 969 ms 136496 KB Output is correct
42 Correct 987 ms 131388 KB Output is correct
43 Correct 1091 ms 146080 KB Output is correct
44 Correct 1016 ms 137760 KB Output is correct
45 Correct 941 ms 151488 KB Output is correct
46 Correct 967 ms 150940 KB Output is correct
47 Correct 1091 ms 147604 KB Output is correct
48 Correct 1091 ms 147356 KB Output is correct
49 Correct 1120 ms 147484 KB Output is correct
50 Correct 1091 ms 147508 KB Output is correct
51 Correct 1220 ms 149924 KB Output is correct
52 Correct 1241 ms 150052 KB Output is correct