Submission #135220

#	Time	Username	Problem	Language	Result	Execution time	Memory
135220		Adhyyan1252	Werewolf (IOI18_werewolf)	C++11	0 / 100	694 ms	111984 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++;
		int ret = 0;
		for(; i > 0; i -= i&(-i)){
			ret += t[i];
		}
		return ret;
	}

	int query(int l, int r){
		return query(r) - 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);
 	}

	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);
 	}


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

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

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

 	//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);
 	}
 	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]){
 			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]]);
 			}
 		}
 	}
 	cout<<"REACHED HERE"<<endl;
 	for(int i = 0; i < n; i++){
 		assert(ans[i] >= 0);
 		ans[i] = ans[i] > 0;
 	}
 	return ans;
}

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