oj.uz

Submission #963716

# Submission time Handle Problem Language Result Execution time Memory
963716 2024-04-15T14:08:04 Z ByeWorld Werewolf (IOI18_werewolf) C++14
34 / 100
 743 ms 80924 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#include <random>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define md ((l+r)>>1)
#define lf (id<<1)
#define rg ((id<<1)|1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 3e5+10;
const int LOG = 19;
const ll INF = 6e18+10;

int n, q;
int ans[MAXN], a[MAXN], idx[MAXN];
vector <int> adj[MAXN];
int st[MAXN][LOG+5], st2[MAXN][LOG+5];

void dfs(int nw, int par, int dep){
	// cout << nw << ' ' << par << " nw\n";
	a[dep] = nw;
	idx[nw] = dep;
	for(auto nx : adj[nw]){
		if(nx == par) continue;
		dfs(nx, nw, dep+1);
	}
}
int MN(int x, int y){
	int lg = log2(y-x+1);
	return min(st[x][lg], st[y-(1<<lg)+1][lg]);
}
int MX(int x, int y){
	int lg = log2(y-x+1);
	return max(st2[x][lg], st2[y-(1<<lg)+1][lg]);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, 
	vector<int> E, vector<int> L, vector<int> R) {
	n = N; q = S.size();
	for(int i=0; i<X.size(); i++){
		adj[X[i]+1].pb(Y[i]+1);
		adj[Y[i]+1].pb(X[i]+1);
	}
	for(int i=1; i<=n; i++){
		if(adj[i].size() == 1){
			dfs(i, -1, 1); break;
		}
	}
	for(int i=1; i<=n; i++){
		st[i][0] = a[i]; st2[i][0] = a[i];
	}
	for(int i=1; i<LOG; i++){
		for(int j=1; j<=n; j++){
			if((j+(1<<(i-1))) > n) st[j][i] = st[j][i-1];
			else st[j][i] = min(st[j][i-1], st[j+(1<<(i-1))][i-1]);

			if((j+(1<<(i-1))) > n) st2[j][i] = st2[j][i-1];
			else st2[j][i] = max(st2[j][i-1], st2[j+(1<<(i-1))][i-1]);
		}
	}
	// for(int i=1; i<=n; i++) cout << a[i] << " \n"[i==n];
// 	cout << " arr\n";
// cout << MN(1, 5) << ' ' << MX(1, 5) << " mx\n";

	for(int i=0; i<q; i++){
		int sta = S[i]+1, en = E[i]+1, le = L[i]+1, ri = R[i]+1;
		if(idx[sta] <= idx[en]){
			// cout << idx[sta] << ' ' << idx[en] << " sa\n";
			int l=idx[sta], r=idx[en], mid=0, cnt=-1;
			while(l<=r){
				mid = md;
				if(MN(idx[sta], mid) >= le){ // masi valid
					l = mid+1; cnt = mid;
				} else r = mid-1;
			}
			l=idx[sta]; r=idx[en]; mid=0; int cnt2=-1;
			while(l<=r){
				mid = md;
				if(MX(mid, idx[en]) <= ri){ // masi valid
					r = mid-1; cnt2 = mid;
				} else l = mid+1;
			}
			// cout << cnt << ' ' << cnt2 << " cntpp\n";

			if(cnt==-1 || cnt2==-1 || cnt<cnt2) ans[i] = 0;
			else ans[i] = 1;
		} else {
			int l=idx[en], r=idx[sta], mid=0, cnt=-1;
			while(l<=r){
				mid = md;
				if(MN(mid, idx[sta]) >= le){ // masi valid
					r = mid-1; cnt = mid;
				} else l = mid+1;
			}
			l=idx[en]; r=idx[sta]; mid=0; int cnt2=-1;
			while(l<=r){
				mid = md;
				if(MX(idx[en], mid) <= ri){ // masi valid
					l = mid+1; cnt2 = mid;
				} else r = mid-1;
			}
			// cout << cnt << ' ' << cnt2 << " cnt\n";
			if(cnt==-1 || cnt2==-1 || cnt>cnt2) ans[i] = 0;
			else ans[i] = 1;
		}
	}

	vector<int> ANS(q);
 	for(int i = 0; i < q; ++i) ANS[i] = ans[i];
  	return ANS;
}

Compilation message

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:44:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i=0; i<X.size(); i++){
      |               ~^~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 57684 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 57684 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 669 ms 80660 KB Output is correct
2 Correct 647 ms 80720 KB Output is correct
3 Correct 664 ms 80720 KB Output is correct
4 Correct 702 ms 80724 KB Output is correct
5 Correct 723 ms 80580 KB Output is correct
6 Correct 735 ms 80632 KB Output is correct
7 Correct 604 ms 80668 KB Output is correct
8 Correct 659 ms 80924 KB Output is correct
9 Correct 321 ms 80680 KB Output is correct
10 Correct 294 ms 80536 KB Output is correct
11 Correct 330 ms 80532 KB Output is correct
12 Correct 344 ms 80796 KB Output is correct
13 Correct 641 ms 80572 KB Output is correct
14 Correct 689 ms 80672 KB Output is correct
15 Correct 630 ms 80672 KB Output is correct
16 Correct 743 ms 80676 KB Output is correct
17 Correct 627 ms 80736 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 57684 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -