oj.uz

Submission #706983

# Submission time Handle Problem Language Result Execution time Memory
706983 2023-03-08T08:18:41 Z Abrar_Al_Samit Werewolf (IOI18_werewolf) C++17
34 / 100
 901 ms 76500 KB 
#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;

const int nax = 2e5 + 10;
vector<int>a[nax], b[nax];
bool vis[nax];

vector<int>stk;
void dfs(int v) {
	vis[v] = 1;
	stk.push_back(v);
	for(int u : a[v]) if(!vis[u]) {
		dfs(u);
	}
}
vector<int>ord;

template<const int type> struct SparseTable {
	int sp[nax][18];
	int N;

	int F(int a, int b) {
		if(type==1) return max(a, b);
		else return min(a, b);
	}
	void build(vector<int>init) {
		N = init.size();
		for(int i=0; i<N; ++i) {
			sp[i][0] = init[i];
		}
		for(int j=1; j<18; ++j) {
			for(int i=0; i+(1<<(j-1))-1<N; ++i) {
				sp[i][j] = F(sp[i][j-1], sp[i+(1<<(j-1))][j-1]);
			}
		}
	}
	pair<int,int>get(int pos, int lim) {
		int l = pos, r = pos;
		for(int j=17; j>=0; --j) {
			int new_pos = l - (1<<j);
			if(new_pos<0) continue;

			if(sp[new_pos][j]<lim && type==2) continue;
			if(sp[new_pos][j]>lim && type==1) continue;
			l = new_pos;
		}
		for(int j=17; j>=0; --j) {
			int new_pos = r + (1<<j);
			if(new_pos>=N) continue;

			if(sp[r][j]<lim && type==2) continue;
			if(sp[r][j]>lim && type==1) continue;

			// if(type==1) {
			// 	cerr<<r<<' '<<new_pos<<'\n';
			// }

			r = new_pos;
		}
		if(sp[l][0]<lim && type==2) ++l;
		else if(sp[l][0]>lim && type==1) ++l;

		if(sp[r][0]<lim && type==2) --r;
		else if(sp[r][0]>lim && type==1) --r;

		return make_pair(l, r);
	}
};
SparseTable<1>big;
SparseTable<2>small;
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();
	vector<int>ans(q);


	for(int i=0; i<m; ++i) {
		a[X[i]].push_back(Y[i]);
		a[Y[i]].push_back(X[i]);
	}

	memset(vis, 0, sizeof vis);
	for(int i=0; i<N; ++i) if(a[i].size()==1) {
		dfs(i);
		ord = stk;
		break;
	}

	//for(int x : ord) cerr<<x<<' '; cerr<<'\n';


	vector<int>invord(N);
	for(int i=0; i<N; ++i) {
		invord[ord[i]] = i;
	}

	big.build(ord), small.build(ord);

	for(int i=0; i<q; ++i) {
		auto [l1, r1] = small.get(invord[S[i]], L[i]);
		auto [l2, r2] = big.get(invord[E[i]], R[i]);

		//cerr<<l1<<' '<<r1<<' '<<l2<<' '<<r2<<'\n';

		if(l1>=l2 && l1<=r2) ans[i] = 1;
		else if(l2>=l1 && l2<=r1) ans[i] = 1;
	}
	return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 901 ms 76384 KB Output is correct
2 Correct 670 ms 76352 KB Output is correct
3 Correct 642 ms 76344 KB Output is correct
4 Correct 628 ms 76352 KB Output is correct
5 Correct 678 ms 76500 KB Output is correct
6 Correct 731 ms 76264 KB Output is correct
7 Correct 680 ms 76352 KB Output is correct
8 Correct 583 ms 76368 KB Output is correct
9 Correct 358 ms 76384 KB Output is correct
10 Correct 377 ms 76464 KB Output is correct
11 Correct 547 ms 76376 KB Output is correct
12 Correct 319 ms 76336 KB Output is correct
13 Correct 690 ms 76288 KB Output is correct
14 Correct 703 ms 76352 KB Output is correct
15 Correct 700 ms 76352 KB Output is correct
16 Correct 675 ms 76384 KB Output is correct
17 Correct 657 ms 76352 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9940 KB Output isn't correct
2 Halted 0 ms 0 KB -