제출 #879121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
879121		Ludissey	늑대인간 (IOI18_werewolf)	C++14	34 / 100	1425 ms	52992 KiB

werewolf

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

using namespace std;
vector<int> indx;
map<int,int> mp;

int N;

struct node {
	node* left, *right;
	int mx;
  int mn; 

	void update() {
		mn = min(left->mn ,right->mn);
		mx = max(left->mx ,right->mx);
 	}
};

node* MAIN_NODE;

pair<int,int> query(node* root, int left, int right, int qLeft, int qRight) {
  if(qLeft>qRight) swap(qLeft, qRight);
	if (left > qRight || right < qLeft) return {-1,-1};
	if (left >= qLeft && right <= qRight) return {root->mn,root->mx};

	int mid = (left + right) / 2;
  pair<int,int> q1=query(root->left, left, mid, qLeft, qRight),q2=query(root->right, mid + 1, right, qLeft, qRight);
  if(q1.first==-1) return {q2.first,q2.second};
  if(q2.first==-1) return {q1.first,q1.second};
	return {min(q1.first,q2.first),max(q1.second,q2.second)};
}

void build(node* root, int left, int right) {
	if (left == right) {
		root->mn = indx[left];
		root->mx = indx[left];
		return;
	}
	int mid = (left + right) / 2;
	root->left = new node{ NULL, NULL, 0, 0 };
	root->right = new node{ NULL, NULL, 0, 0 };
	build(root->left, left, mid);
	build(root->right, mid+1, right);
	root->update();
}

void destroy(node* root) {
	if (root->left) destroy(root->left);
	if (root->right) destroy(root->right);
	delete root;
}

bool bsta(int s, int e, int L, int R){
  s=mp[s];
  e=mp[e];
  int l=s, r=e;
  if(l>r) swap(l,r);
  while(l<r){
    int mid=((l+r+1)/2);
    int qH,qW;
    qH=query(MAIN_NODE, 0, N-1, s,mid).first;
    qW=query(MAIN_NODE, 0, N-1, mid,e).second;
    if(qH<L&&qW>R) return false;
    else if(qH<L) {
      if(s>e) l=mid+1;
      else r=mid-1;
    } else if(qW>R){
      if(s>e) r=mid-1;
      else l=mid+1;
    }else{
      return true;
    }
  }
  int qH,qW;
  qH=query(MAIN_NODE, 0, N-1, s,l).first;
  qW=query(MAIN_NODE, 0, N-1, l,e).second;
  if(qH<L||qW>R) return false;
  return true;
}

std::vector<int> check_validity(signed n, std::vector<signed> X, std::vector<signed> Y,  std::vector<signed> S, std::vector<signed> E, std::vector<signed> L, std::vector<signed> R) {
  N=n;
  int Q = S.size();
  std::vector<int> A(Q);
  indx.resize(N);
  int leaf=0;
  vector<vector<int>> adj(N);
  for (int i = 0; i < n-1; i++) { adj[X[i]].push_back(Y[i]); adj[Y[i]].push_back(X[i]);}
  for (int i = 0; i < N; i++) if(adj[i].size()==1) { leaf=i; break; }
  indx[0]=leaf;
  indx[1]=adj[leaf][0];
  mp[indx[0]]=0;
  mp[indx[1]]=1;
  for (int i = 2; i < N; i++) 
  {
    if(adj[indx[i-1]][0]==indx[i-2]) indx[i]=adj[indx[i-1]][1];
    else indx[i]=adj[indx[i-1]][0];
    mp[indx[i]]=i;
  }
  MAIN_NODE=new node{NULL, NULL, 0, 0};
  build(MAIN_NODE, 0, N-1);
  for (int i = 0; i < Q; ++i) {
    A[i] = bsta(S[i],E[i],L[i],R[i]);
  }
  return A;
}

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