Submission #1147420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147420		Kaztaev_Alisher	Werewolf (IOI18_werewolf)	C++20	49 / 100	4094 ms	87348 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second

using namespace std;
using ll = long long;

const ll N = 1e6+5 , inf = 2e9 + 7 , block = 1000;
const ll INF = 1e18 ,   mod = 1e9+7;

int p[N][2] , sz[N][2];
int get(int a , int k){
	if(p[a][k] == a) return a;
	return p[a][k] = get(p[a][k],k);
}
void merge(int a , int b , int k){
	a = get(a,k);
	b = get(b,k);
	if(a == b) return;
	if(sz[a][k] < sz[b][k]) swap(a,b);
	sz[a][k] += sz[b][k];
	p[b][k] = a;
}
vector<int> g[N] , ord;
int spmn[N][20] , spmx[N][20] , lg[N] , pos[N];

void dfs(int v, int p){
	ord.push_back(v);
	for(int to : g[v]){
		if(to != p) dfs(to,v);
	}
}
void go(int n){
	for(int i = 0; i < n; i++){
		if(g[i].size() == 1){
			dfs(i,0);
			break;
		}
	}
	for(int i = 0; i < ord.size(); i++){
		pos[ord[i]] = i;
	}
	for(int i = 1; i <= n; i++){
		lg[i] = lg[i/2]+1;
		if(i == 1) lg[i] = 0;
	}
	for(int i = 0; i < n; i++){
		spmn[i][0] = spmx[i][0] = ord[i];
	}
	for(int j = 1; j <= lg[n]; j++){
		for(int i = 0; i + (1 << j) -1 < n; i++){
			spmn[i][j] = min(spmn[i][j-1] , spmn[i+(1 << (j-1))][j-1]);
			spmx[i][j] = max(spmx[i][j-1] , spmx[i+(1 << (j-1))][j-1]);
		}
	}
}
int getmx(int l , int r){
	int len = lg[r-l+1];
	return max(spmx[l][len] , spmx[r-(1 << len)+1][len]);
}
int getmn(int l , int r){
	int len = lg[r-l+1];
	return min(spmn[l][len] , spmn[r-(1 << len)+1][len]);
}
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e , vector<int> l, vector<int> r) {
	vector<int> ans;
	for(int i = 0; i < x.size(); i++){
		g[x[i]].push_back(y[i]);
		g[y[i]].push_back(x[i]);
	}
	int cnt = 0 , cnt2 = 0;
	for(int i = 0; i < n; i++){
		if(g[i].size() == 1) cnt++;
		else if(g[i].size() == 2) cnt2++;
	}
	if(cnt == 2 && cnt2 == n-2){
		go(n);
		for(int i = 0; i < s.size(); i++){
			if(pos[s[i]] < pos[e[i]]){
				int L = pos[s[i]] , R = pos[e[i]] , res = pos[s[i]];
				while(L <= R){
					int md = (L+R) >> 1;
					if(getmn(L,md) >= l[i]){
						res = md;
						L = md+1;
					} else {
						R = md-1;
					}
				}
				int res1 = pos[e[i]];
				L = pos[s[i]] , R = pos[e[i]];
				while(L <= R){
					int md = (L+R) >> 1;
					if(getmx(md,R) <= r[i]){
						res1 = md;
						R = md-1;
					} else {
						L = md+1;
					}
				}
				if(res >= res1){
					ans.push_back(1);
				} else {
					ans.push_back(0);
				}
			} else {
				int L = pos[e[i]] , R = pos[s[i]] , res = pos[e[i]];
				while(L <= R){
					int md = (L+R) >> 1;
					if(getmx(L,md) <= r[i]){
						res = md;
						L = md+1;
					} else {
						R = md-1;
					}
				}
				int res1 = pos[s[i]];
				L = pos[e[i]] , R = pos[s[i]];
				while(L <= R){
					int md = (L+R) >> 1;
					if(getmn(md,R) >= l[i]){
						res1 = md;
						R = md-1;
					} else {
						L = md+1;
					}
				}
				if(res >= res1){
					ans.push_back(1);
				} else {
					ans.push_back(0);
				}
			}
		}
	} else {
		for(int i = 0; i < s.size(); i++){
			for(int j = 0; j < n; j++){
				p[j][0] = p[j][1] = j;
				sz[j][0] = sz[j][1] = 1;
			}
			for(int j = 0; j < x.size(); j++){
				if(x[j] >= l[i] && y[j] >= l[i]){
					merge(x[j],y[j],0);
				}
				if(x[j] <= r[i] && y[j] <= r[i]){
					merge(x[j],y[j],1);
				}
			}
			int ok = 0;
			for(int j = 0; j < n; j++){
				if(get(s[i] , 0) == get(j , 0) && get(e[i] , 1) == get(j , 1)){
					ok = 1;
					break;
				}
			}
			ans.push_back(ok);
		}
	}
	return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51