Submission #963716

#	Time	Username	Problem	Language	Result	Execution time	Memory
963716		ByeWorld	늑대인간 (IOI18_werewolf)	C++14	34 / 100	743 ms	80924 KiB

werewolf

#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 (stderr)

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
• Subtask 2: 0 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51