oj.uz

Submission #879121

# Submission time Handle Problem Language Result Execution time Memory
879121 2023-11-26T11:57:29 Z Ludissey Werewolf (IOI18_werewolf) C++14
34 / 100
 1425 ms 52992 KB 
#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.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 726 ms 44292 KB Output is correct
2 Correct 641 ms 52620 KB Output is correct
3 Correct 746 ms 52520 KB Output is correct
4 Correct 1224 ms 52720 KB Output is correct
5 Correct 1425 ms 52720 KB Output is correct
6 Correct 1424 ms 52820 KB Output is correct
7 Correct 980 ms 52488 KB Output is correct
8 Correct 517 ms 52744 KB Output is correct
9 Correct 470 ms 52728 KB Output is correct
10 Correct 547 ms 52488 KB Output is correct
11 Correct 911 ms 52840 KB Output is correct
12 Correct 685 ms 52560 KB Output is correct
13 Correct 657 ms 52564 KB Output is correct
14 Correct 650 ms 52620 KB Output is correct
15 Correct 680 ms 52992 KB Output is correct
16 Correct 720 ms 52716 KB Output is correct
17 Correct 965 ms 52716 KB Output is correct

Subtask #4
0 / 51.0

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