oj.uz

답안 #135240

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
135240 2019-07-23T21:14:53 Z Adhyyan1252 늑대인간 (IOI18_werewolf) C++11
15 / 100
 4000 ms 51344 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 452 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 452 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 25 ms 1228 KB Output is correct
11 Correct 19 ms 1144 KB Output is correct
12 Correct 8 ms 1100 KB Output is correct
13 Correct 16 ms 1400 KB Output is correct
14 Correct 9 ms 1412 KB Output is correct
15 Correct 15 ms 1272 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 700 ms 45660 KB Output is correct
2 Execution timed out 4045 ms 51344 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 452 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 25 ms 1228 KB Output is correct
11 Correct 19 ms 1144 KB Output is correct
12 Correct 8 ms 1100 KB Output is correct
13 Correct 16 ms 1400 KB Output is correct
14 Correct 9 ms 1412 KB Output is correct
15 Correct 15 ms 1272 KB Output is correct
16 Correct 700 ms 45660 KB Output is correct
17 Execution timed out 4045 ms 51344 KB Time limit exceeded
18 Halted 0 ms 0 KB -