oj.uz

Submission #135242

# Submission time Handle Problem Language Result Execution time Memory
135242 2019-07-23T21:15:19 Z Adhyyan1252 Werewolf (IOI18_werewolf) C++11
100 / 100
 865 ms 73132 KB 
#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

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.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 8 ms 1144 KB Output is correct
11 Correct 8 ms 1016 KB Output is correct
12 Correct 8 ms 1016 KB Output is correct
13 Correct 8 ms 1272 KB Output is correct
14 Correct 8 ms 1272 KB Output is correct
15 Correct 9 ms 1144 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 624 ms 45584 KB Output is correct
2 Correct 635 ms 51380 KB Output is correct
3 Correct 627 ms 48044 KB Output is correct
4 Correct 593 ms 46384 KB Output is correct
5 Correct 590 ms 46256 KB Output is correct
6 Correct 792 ms 46256 KB Output is correct
7 Correct 564 ms 45148 KB Output is correct
8 Correct 619 ms 51852 KB Output is correct
9 Correct 521 ms 48664 KB Output is correct
10 Correct 521 ms 44812 KB Output is correct
11 Correct 530 ms 44900 KB Output is correct
12 Correct 573 ms 47272 KB Output is correct
13 Correct 627 ms 56384 KB Output is correct
14 Correct 632 ms 56468 KB Output is correct
15 Correct 646 ms 56368 KB Output is correct
16 Correct 647 ms 56428 KB Output is correct
17 Correct 621 ms 45616 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 8 ms 1144 KB Output is correct
11 Correct 8 ms 1016 KB Output is correct
12 Correct 8 ms 1016 KB Output is correct
13 Correct 8 ms 1272 KB Output is correct
14 Correct 8 ms 1272 KB Output is correct
15 Correct 9 ms 1144 KB Output is correct
16 Correct 624 ms 45584 KB Output is correct
17 Correct 635 ms 51380 KB Output is correct
18 Correct 627 ms 48044 KB Output is correct
19 Correct 593 ms 46384 KB Output is correct
20 Correct 590 ms 46256 KB Output is correct
21 Correct 792 ms 46256 KB Output is correct
22 Correct 564 ms 45148 KB Output is correct
23 Correct 619 ms 51852 KB Output is correct
24 Correct 521 ms 48664 KB Output is correct
25 Correct 521 ms 44812 KB Output is correct
26 Correct 530 ms 44900 KB Output is correct
27 Correct 573 ms 47272 KB Output is correct
28 Correct 627 ms 56384 KB Output is correct
29 Correct 632 ms 56468 KB Output is correct
30 Correct 646 ms 56368 KB Output is correct
31 Correct 647 ms 56428 KB Output is correct
32 Correct 621 ms 45616 KB Output is correct
33 Correct 865 ms 55224 KB Output is correct
34 Correct 342 ms 34820 KB Output is correct
35 Correct 700 ms 59312 KB Output is correct
36 Correct 683 ms 54960 KB Output is correct
37 Correct 709 ms 57984 KB Output is correct
38 Correct 692 ms 55808 KB Output is correct
39 Correct 658 ms 72108 KB Output is correct
40 Correct 733 ms 66128 KB Output is correct
41 Correct 666 ms 57320 KB Output is correct
42 Correct 544 ms 55932 KB Output is correct
43 Correct 748 ms 64916 KB Output is correct
44 Correct 664 ms 58024 KB Output is correct
45 Correct 572 ms 73132 KB Output is correct
46 Correct 586 ms 72864 KB Output is correct
47 Correct 725 ms 64040 KB Output is correct
48 Correct 648 ms 63916 KB Output is correct
49 Correct 681 ms 64044 KB Output is correct
50 Correct 721 ms 63896 KB Output is correct
51 Correct 822 ms 63916 KB Output is correct
52 Correct 721 ms 63688 KB Output is correct