oj.uz

Submission #228348

# Submission time Handle Problem Language Result Execution time Memory
228348 2020-04-30T16:26:07 Z rqi Werewolf (IOI18_werewolf) C++14
100 / 100
 2189 ms 205528 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 

typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 

typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 

#define mp make_pair 
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 

template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; } 
int pct(int x) { return __builtin_popcount(x); } 
int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 

// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);

template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }

template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }

// TO_STRING
#define ts to_string
template<class A, class B> str ts(pair<A,B> p);
template<class A> str ts(complex<A> c) { return ts(mp(c.real(),c.imag())); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(char c) { str s = ""; s += c; return s; }
str ts(str s) { return s; }
str ts(const char* s) { return (str)s; }
str ts(vector<bool> v) { 
	bool fst = 1; str res = "{";
	F0R(i,sz(v)) {
		if (!fst) res += ", ";
		fst = 0; res += ts(v[i]);
	}
	res += "}"; return res;
}
template<size_t SZ> str ts(bitset<SZ> b) {
	str res = ""; F0R(i,SZ) res += char('0'+b[i]);
	return res; }
template<class T> str ts(T v) {
	bool fst = 1; str res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += ts(x);
	}
	res += "}"; return res;
}
template<class A, class B> str ts(pair<A,B> p) {
	return "("+ts(p.f)+", "+ts(p.s)+")"; }

// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
	pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
	pr(h); if (sizeof...(t)) pr(" "); ps(t...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
	unsyncIO();
	// cin.exceptions(cin.failbit); 
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 


/**
 * Description: point add and rectangle sum with offline 2D BIT. $x\in (0,SZ)$.
 * Time: O(N\log^2 N)
 * Memory: O(N\log N)
 * Source: Own
 * Verification: 
 	* https://dmoj.ca/problem/occ19g4
 	* http://www.usaco.org/index.php?page=viewproblem2&cpid=722 (753 ms)
 	* http://www.usaco.org/index.php?page=viewproblem2&cpid=601 (679 ms)
 */

template<class T, int SZ> struct OffBIT2D { 
	bool mode = 0; // mode = 1 -> initialized
	vpi todo;
	int cnt[SZ], st[SZ];
	vi val, bit;
	void init() {
		assert(!mode); mode = 1;
		int lst[SZ]; F0R(i,SZ) lst[i] = cnt[i] = 0;
		sort(all(todo),[](const pi& a, const pi& b) { 
			return a.s < b.s; });
		trav(t,todo) for (int x = t.f; x < SZ; x += x&-x) 
			if (lst[x] != t.s) lst[x] = t.s, cnt[x] ++;
		int sum = 0;
		F0R(i,SZ) { lst[i] = 0; st[i] = sum; sum += cnt[i]; }
		val.rsz(sum); bit.rsz(sum); // store BITs in single vector
		trav(t,todo) for (int x = t.f; x < SZ; x += x&-x) 
			if (lst[x] != t.s) lst[x] = t.s, val[st[x]++] = t.s;
	}
	int rank(int y, int l, int r) {
		return ub(begin(val)+l,begin(val)+r,y)-begin(val)-l; }
	void UPD(int x, int y, int t) {
		int z = st[x]-cnt[x]; // x-BIT = range from z to st[x]-1
		for (y = rank(y,z,st[x]); y <= cnt[x]; y += y&-y) 
			bit[z+y-1] += t;
	}
	void upd(int x, int y, int t) { 
		if (!mode) todo.pb({x,y});
		else for (; x < SZ; x += x&-x) UPD(x,y,t); 
	}
	int QUERY(int x, int y) {
		int z = st[x]-cnt[x], res = 0;
		for (y = rank(y,z,st[x]); y; y -= y&-y) res += bit[z+y-1];
		return res;
	}
	int query(int x, int y) { 
		assert(mode);
		int res = 0; for (; x; x -= x&-x) res += QUERY(x,y);
		return res;
	}
	int query(int xl, int xr, int yl, int yr) { 
		return query(xr,yr)-query(xl-1,yr)
			-query(xr,yl-1)+query(xl-1,yl-1); }
};



/**
 * Description: 1D range minimum query. Can also do queries 
 	* for any associative operation in $O(1)$ with D\&C
 * Source: KACTL
 * Verification: 
	* https://cses.fi/problemset/stats/1647/
	* http://wcipeg.com/problem/ioi1223
	* https://pastebin.com/ChpniVZL
 * Memory: O(N\log N)
 * Time: O(1)
 */

template<class T> struct RMQ { // floor(log_2(x))
	int level(int x) { return 31-__builtin_clz(x); } 
	vector<T> v; vector<vi> jmp;
	int comb(int a, int b) { // index of min
		return v[a]==v[b]?min(a,b):(v[a]<v[b]?a:b); } 
	void init(const vector<T>& _v) {
		v = _v; jmp = {vi(sz(v))}; iota(all(jmp[0]),0);
		for (int j = 1; 1<<j <= sz(v); ++j) {
			jmp.pb(vi(sz(v)-(1<<j)+1));
			F0R(i,sz(jmp[j])) jmp[j][i] = comb(jmp[j-1][i],
									jmp[j-1][i+(1<<(j-1))]);
		}
	}
	int index(int l, int r) { // get index of min element
		int d = level(r-l+1);
		return comb(jmp[d][l],jmp[d][r-(1<<d)+1]); }
	T query(int l, int r) { return v[index(l,r)]; }
};

/**
 * Description: Euler Tour LCA w/ O(1) query. Compress takes a subset $S$ 
 	* of nodes and computes the minimal subtree that contains all the nodes 
	* pairwise LCA's and compressing edges. Returns a list of (par, orig\_index) 
	* representing a tree rooted at 0. The root points to itself.
 * Source: USACO, Simon Lindholm (KACTL)
 * Verification: USACO Debug the Bugs
 	* https://codeforces.com/contest/1320/problem/E
 */


template<int SZ> struct LCA {
	int N, R = 1, depth[SZ], st[SZ], en[SZ];
	vi adj[SZ]; vpi tmp; RMQ<pi> r;
	void ae(int u, int v) { adj[u].pb(v), adj[v].pb(u); }
	void dfs(int u, int prev){
		en[u] = st[u] = sz(tmp), depth[u] = depth[prev]+1;
		tmp.pb({depth[u],u});
		trav(v,adj[u]) if (v != prev){
			dfs(v,u);
			en[u] = sz(tmp);
			tmp.pb({depth[u],u});
		}
			
	}
	void init(int _N) { N = _N; dfs(R,0); r.init(tmp); }
	int lca(int u, int v){
		u = st[u], v = st[v]; if (u > v) swap(u,v);
		return r.query(u,v).s; }
	/// int dist(int u, int v) {
		/// return depth[u]+depth[v]-2*depth[lca(u,v)]; }
	vpi compress(vi S) {
		static vi rev; rev.rsz(N+1);
		auto cmp = [&](int a, int b) { return st[a] < st[b]; };
		sort(all(S),cmp);
		int m = sz(S)-1; F0R(i,m) S.pb(lca(S[i],S[i+1]));
		sort(all(S),cmp); S.erase(unique(all(S)),end(S));
		F0R(i,sz(S)) rev[S[i]] = i;
		vpi ret = {pi(0,S[0])};
		F0R(i,sz(S)-1) ret.eb(rev[lca(S[i],S[i+1])],S[i+1]);
		return ret;
	}
};


/**
 * Description: Disjoint Set Union with path compression. 
 	* Add edges and test connectivity. Use for Kruskal's 
 	* minimum spanning tree.
 * Time: O(\alpha(N))
 * Source: CSAcademy, KACTL
 * Verification: USACO superbull
 */

struct DSU {
	vi e; void init(int n) { e = vi(n,-1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } 
	bool sameSet(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) { // Attach y to x
		x = get(x), y = get(y); if (x == y) return 0;
		e[x] += e[y]; e[y] = x; return 1;
	}
};

/**template<class T> T kruskal(int n, vector<pair<T,pi>> ed) {
	sort(all(ed));
	T ans = 0; DSU D; D.init(n+1); // edges that unite are in MST
	trav(a,ed) if (D.unite(a.s.f,a.s.s)) ans += a.f; 
	return ans;
}*/

const int mx = 200005;
vi uadj[mx];
vi dadj[mx];
int par1[mx][25];
int par2[mx][25];
LCA<mx> lca1;
LCA<mx> lca2;
OffBIT2D<int, 2*mx+10> points;

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {

	int Q = S.size();
	int M = X.size();

	for(int i = 0; i < M; i++){
		X[i]++;
		Y[i]++;
	}
	for(int i = 0; i < Q; i++){
		S[i]++;
		E[i]++;
		L[i]++;
		R[i]++;
	}

	for(int i = 0; i < M; i++){
		int a = X[i];
		int b = Y[i];
		if(a > b) swap(a, b);
		uadj[a].pb(b);
		dadj[b].pb(a);
	}

	DSU dsu;
	dsu.init(N+5);
	for(int i = N; i >= 1; i--){
		for(auto u: uadj[i]){
			if(dsu.sameSet(i, u)) continue;
			u = dsu.get(u);
			par1[u][0] = i;
			//ps(u, i);
			lca1.ae(u, i);
			dsu.unite(i, u);
		}
	}
	//ps("SEP");
	dsu.init(N+5);
	for(int i = 1; i <= N; i++){
		for(auto u: dadj[i]){
			if(dsu.sameSet(i, u)) continue;
			u = dsu.get(u);
			par2[u][0] = i;
			lca2.ae(u, i);
			//ps(u, i);
			dsu.unite(i, u);
		}
	}



	for(int j = 1; j <= 20; j++){
		for(int i = 1; i <= N; i++){
			par1[i][j] = par1[par1[i][j-1]][j-1];
			par2[i][j] = par2[par2[i][j-1]][j-1];
		}
	}


	lca1.init(N);
	lca2.R = N;
	lca2.init(N);

	//ps(par1[4][0]);

	vpi a;

	for(int i = 1; i <= N; i++){
		points.upd(lca1.st[i]+1, lca2.st[i]+1, 1);
		a.pb(mp(lca1.st[i]+1, lca2.st[i]+1));
		//ps(i, lca1.st[i]+1, lca2.st[i]+1, 1);
	}

	points.init();

	for(auto u: a){
		//ps(u.f, u.s, 1);
		points.upd(u.f, u.s, 1);
	}

	vi A;

	

	for(int i = 0; i < Q; i++){
		int ind1 = L[i];
		int pos1 = S[i];
		//ps(i, ind1, pos1);
		for(int j = 20; j >= 0; j--){
			if(par1[pos1][j] == 0) continue;
			if(par1[pos1][j] >= ind1){
				//ps(pos1, par1[pos1][j]);
				pos1 = par1[pos1][j];
			}
		}
		int ind2 = R[i];
		int pos2 = E[i];
		for(int j = 20; j >= 0; j--){
			if(par2[pos2][j] == 0) continue;
			if(par2[pos2][j] <= ind2){
				pos2 = par2[pos2][j];
			}
		}
		//ps(pos1, pos2);
		//subtree of pos1 in tree1
		int st1 = lca1.st[pos1];
		int en1 = lca1.en[pos1];
		//subtree of pos2 in tree2
		int st2 = lca2.st[pos2];
		int en2 = lca2.en[pos2];
		//ps(st1+1, en1+1, st2+1, en2+1);
		if(points.query(st1+1, en1+1, st2+1, en2+1) == 0){
			A.pb(0);
		}
		else A.pb(1);
	}
	


  	return A;
}

/*int main(){
	int N, M, Q;
	cin >> N >> M >> Q;
	vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
	for (int j = 0; j < M; ++j) {
    cin >> X[j];
    cin >> Y[j];
  }
  for (int i = 0; i < Q; ++i) {
    cin >> S[i];
    cin >> E[i];
    cin >> L[i];
    cin >> R[i];
  }
  vi a = (check_validity(N, X, Y, S, E, L, R));
  for(auto u: a){
  	ps(u);
  }
}*/

Compilation message

werewolf.cpp: In function 'void setIn(std::__cxx11::string)':
werewolf.cpp:124:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
werewolf.cpp: In function 'void setOut(std::__cxx11::string)':
werewolf.cpp:125:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23936 KB Output is correct
2 Correct 19 ms 23936 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 18 ms 23808 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct
6 Correct 19 ms 23936 KB Output is correct
7 Correct 21 ms 23936 KB Output is correct
8 Correct 19 ms 23936 KB Output is correct
9 Correct 19 ms 23936 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23936 KB Output is correct
2 Correct 19 ms 23936 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 18 ms 23808 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct
6 Correct 19 ms 23936 KB Output is correct
7 Correct 21 ms 23936 KB Output is correct
8 Correct 19 ms 23936 KB Output is correct
9 Correct 19 ms 23936 KB Output is correct
10 Correct 33 ms 26240 KB Output is correct
11 Correct 31 ms 26240 KB Output is correct
12 Correct 31 ms 26240 KB Output is correct
13 Correct 32 ms 26360 KB Output is correct
14 Correct 32 ms 26240 KB Output is correct
15 Correct 31 ms 26548 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1744 ms 188324 KB Output is correct
2 Correct 1647 ms 197788 KB Output is correct
3 Correct 1506 ms 196312 KB Output is correct
4 Correct 1498 ms 196312 KB Output is correct
5 Correct 1463 ms 196240 KB Output is correct
6 Correct 1690 ms 196476 KB Output is correct
7 Correct 1560 ms 196460 KB Output is correct
8 Correct 1614 ms 197812 KB Output is correct
9 Correct 1143 ms 196308 KB Output is correct
10 Correct 1140 ms 196396 KB Output is correct
11 Correct 1214 ms 196344 KB Output is correct
12 Correct 1265 ms 196292 KB Output is correct
13 Correct 1482 ms 203724 KB Output is correct
14 Correct 1457 ms 203564 KB Output is correct
15 Correct 1463 ms 203576 KB Output is correct
16 Correct 1471 ms 203688 KB Output is correct
17 Correct 1516 ms 196372 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23936 KB Output is correct
2 Correct 19 ms 23936 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 18 ms 23808 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct
6 Correct 19 ms 23936 KB Output is correct
7 Correct 21 ms 23936 KB Output is correct
8 Correct 19 ms 23936 KB Output is correct
9 Correct 19 ms 23936 KB Output is correct
10 Correct 33 ms 26240 KB Output is correct
11 Correct 31 ms 26240 KB Output is correct
12 Correct 31 ms 26240 KB Output is correct
13 Correct 32 ms 26360 KB Output is correct
14 Correct 32 ms 26240 KB Output is correct
15 Correct 31 ms 26548 KB Output is correct
16 Correct 1744 ms 188324 KB Output is correct
17 Correct 1647 ms 197788 KB Output is correct
18 Correct 1506 ms 196312 KB Output is correct
19 Correct 1498 ms 196312 KB Output is correct
20 Correct 1463 ms 196240 KB Output is correct
21 Correct 1690 ms 196476 KB Output is correct
22 Correct 1560 ms 196460 KB Output is correct
23 Correct 1614 ms 197812 KB Output is correct
24 Correct 1143 ms 196308 KB Output is correct
25 Correct 1140 ms 196396 KB Output is correct
26 Correct 1214 ms 196344 KB Output is correct
27 Correct 1265 ms 196292 KB Output is correct
28 Correct 1482 ms 203724 KB Output is correct
29 Correct 1457 ms 203564 KB Output is correct
30 Correct 1463 ms 203576 KB Output is correct
31 Correct 1471 ms 203688 KB Output is correct
32 Correct 1516 ms 196372 KB Output is correct
33 Correct 2110 ms 196112 KB Output is correct
34 Correct 454 ms 54776 KB Output is correct
35 Correct 2172 ms 198256 KB Output is correct
36 Correct 2072 ms 196708 KB Output is correct
37 Correct 2189 ms 197240 KB Output is correct
38 Correct 2144 ms 197008 KB Output is correct
39 Correct 1801 ms 204340 KB Output is correct
40 Correct 1595 ms 205528 KB Output is correct
41 Correct 2008 ms 196564 KB Output is correct
42 Correct 1361 ms 196720 KB Output is correct
43 Correct 2169 ms 203260 KB Output is correct
44 Correct 2145 ms 197256 KB Output is correct
45 Correct 1527 ms 204728 KB Output is correct
46 Correct 1639 ms 204448 KB Output is correct
47 Correct 1454 ms 203896 KB Output is correct
48 Correct 1440 ms 203760 KB Output is correct
49 Correct 1474 ms 203848 KB Output is correct
50 Correct 1459 ms 203880 KB Output is correct
51 Correct 1478 ms 205216 KB Output is correct
52 Correct 1504 ms 205192 KB Output is correct