Submission #135242

#	Time	Username	Problem	Language	Result	Execution time	Memory
135242		Adhyyan1252	Werewolf (IOI18_werewolf)	C++11	100 / 100	865 ms	73132 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> ii;
#define cout if(false) cout
struct dsu{
	vector<int> par;
	int sz;
	dsu(int size){
		sz = size;
		par = vector<int>(sz, -1);
	}

	int find(int cur){
		if(par[cur] == -1) return cur;
		return par[cur] = find(par[cur]);
	}

	bool merge(int a, int b){
		a = find(a);
		b = find(b);
		if(a == b) return false;
		par[a] = b;
		return true;
	}
};


vector<vector<int> > g;
int tym = 0;

void eulerTour(int cur, vector<vector<int> >&G, vector<int>& arr, vector<int>& sl, vector<int>& el){
	tym++;
	sl[cur] = tym; 
	arr.push_back(cur);
	for(int u: G[cur]){
		eulerTour(u, G, arr, sl, el);
	}
	el[cur] = tym;
}


struct bit{
	vector<int> t;
	int sz;
	bit(int size){
		sz = size;
		t = vector<int>(sz+1, 0);
	}

	int query(int i){
		i++;
		cout<<"Q: "<<i<<endl;
		assert(i > 0 && i <= sz);
		int ret = 0;
		for(; i > 0; i -= i&(-i)){
			ret += t[i];
		}
		return ret;
	}

	int query(int l, int r){
		return query(r) - (l==0?0:query(l-1));
	}

	void upd(int i, int val){
		i++;
		for(; i <= sz; i += i&(-i)){
			t[i] += val;
		}
	}
};

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();
	g.resize(n);
	for(int i = 0; i < m; i++){
		g[x[i]].push_back(y[i]);
		g[y[i]].push_back(x[i]);
	}
	cout<<"REACHED HERE"<<endl;
  //doing this for L
	vector<int> lpar(Q);
	vector<int> eulerLeft, startL(n), endL(n);
  	{
		vector<vector<int> > eventL(n);
		for(int i = 0; i < Q; i++){
			eventL[L[i]].push_back(i);
		}

		vector<vector<int> > gl(n);
		dsu dl(n);
		for(int i = n-1; i >= 0; i--){
			//add node i
			for(int u: g[i]){
				if(u < i) continue;
				int par= dl.find(u);
				if(par == i) continue;

				gl[i].push_back(par);
				dl.merge(par, i);
			}

			//node added, now find parents for all those
			for(int u: eventL[i]){
				int p = dl.find(S[u]);
				lpar[u] = p;
			}
		}

		cout<<"GRAPH HERE"<<endl;
		// for(int i = 0; i < n; i++){
		// 	cout<<i<<" : ";
		// 	for(int u: gl[i]){
		// 		cout<<u<<" ";
		// 	}
		// 	cout<<endl;
		// }
		tym = -1;
		eulerTour(0, gl, eulerLeft, startL, endL);
		assert(eulerLeft.size() == n);
 	}

	cout<<"REACHED HERE"<<endl;
 	//doing this for R
	vector<int> rpar(Q);
	vector<int> eulerRight, startR(n), endR(n);
  	{
		vector<vector<int> > eventR(n);
		for(int i = 0; i < Q; i++){
			eventR[R[i]].push_back(i);
		}

		vector<vector<int> > gl(n);
		dsu dl(n);
		for(int i = 0; i < n; i++){
			//add node i
			for(int u: g[i]){
				if(u > i) continue;
				int par= dl.find(u);
				if(par == i) continue;

				gl[i].push_back(par);
				dl.merge(par, i);
			}

			//node added, now find parents for all those
			for(int u: eventR[i]){
				int p = dl.find(E[u]);
				rpar[u] = p;
			}
		}
		cout<<"GRAPH HERE"<<endl;
		// for(int i = 0; i < n; i++){
		// 	cout<<i<<" : ";
		// 	for(int u: gl[i]){
		// 		cout<<u<<" ";
		// 	}
		// 	cout<<endl;
		// }
		tym = -1;
		eulerTour(n-1, gl, eulerRight, startR, endR);
		assert(eulerRight.size() == n); 
	}


 	//found euler tour array for both. need to check for intersection for each query
 	//find inverse permutation now
 	cout<<"REACHED HERE"<<endl;

 	cout<<"EULER TOUR"<<endl;
 	for(int i = 0; i < n; i++){
 		cout<<eulerLeft[i]<<" ";
 		assert(eulerLeft[i] < n && eulerLeft[i] >= 0);
 	}
 	cout<<endl;
 	for(int i = 0; i < n; i++){
 		cout<<eulerRight[i]<<" ";
 		assert(eulerRight[i] < n && eulerRight[i] >= 0);
 	}
 	cout<<endl;

 	vector<int> rev(n);
 	for(int i = 0; i < n; i++){
 		assert(rev[eulerRight[i]] == 0);
 		rev[eulerRight[i]] = i;
 	}	
 	vector<int> arr(n);
 	for(int i = 0; i < n; i++){
 		arr[i] = rev[eulerLeft[i]];
 		assert(arr[i] >= 0 && arr[i] < n);
 	}

 	//now arr is the one we care about
 	//need to check whether in box there is atleast one
 	cout<<"DONE ALL "<<endl;
 	vector<vector<int> > events(n);
 	for(int i = 0; i < Q; i++){
 		cout<<i<<" "<<lpar[i]<<" "<<startL[lpar[i]]<<" "<<endL[lpar[i]]<<endl;
 		if(startL[lpar[i]]-1 >= 0) events[startL[lpar[i]]-1].push_back(i);
 		events[endL[lpar[i]]].push_back(i);
 		assert(endL[lpar[i]] < n && endL[lpar[i]] >= 0);
 	}
 	cout<<"REACHED HERE"<<endl;
 	vector<int> ans(Q);
 	bit b(n);
 	for(int i = 0; i < n; i++){
 		b.upd(arr[i], 1);
 		for(int u: events[i]){
 			assert(endR[rpar[u]] < n && endR[rpar[u]] >= 0);
 			cout<<"RPAR "<<u<<" "<<rpar[u]<<" "<<startR[rpar[u]]<<endl;
 			if(endL[lpar[u]] == i){ //exiting
 				ans[u] += b.query(startR[rpar[u]], endR[rpar[u]]);
 			}else{
 				ans[u] -= b.query(startR[rpar[u]], endR[rpar[u]]);
 			}
 		}
 	}

 	// for(int i = 0; i < Q; i++){
 	// 	for(int l = startL[lpar[i]]; l <= endL[lpar[i]]; l++){
 	// 		if(arr[l] >= startR[rpar[i]] && arr[l] <= endR[rpar[i]]){
 	// 			ans[i]++;
 	// 		}
 	// 	}
 	// }

 	cout<<"REACHED HERE"<<endl;
 	for(int i = 0; i < Q; i++){
 		assert(ans[i] >= 0);
 		ans[i] = ans[i] > 0;
 	}
 	return ans;
}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from werewolf.cpp:2:
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:124:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(eulerLeft.size() == n);
          ~~~~~~~~~~~~~~~~~^~~~
werewolf.cpp:166:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(eulerRight.size() == n); 
          ~~~~~~~~~~~~~~~~~~^~~~

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