oj.uz

답안 #821792

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
821792 2023-08-11T16:46:07 Z Trumling 늑대인간 (IOI18_werewolf) C++14
34 / 100
 810 ms 41820 KB 
#include<bits/stdc++.h>
#include "werewolf.h"
#include <cstdio>
#include <cstdlib>
#include <time.h>
#include <stdlib.h>

using namespace std; 

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()
struct node
{
ll min,max;
};

node seg[800000];
ll arr[200000];

void build(int l,int r,int idx)
{
  if(l==r)
  {
    seg[idx]={arr[l],arr[l]};
    return ;
  }

  build(l,(l+r)/2,idx*2);
  build((l+r)/2+1,r,idx*2+1);

  seg[idx].min=min(seg[idx*2].min,seg[idx*2+1].min);
  seg[idx].max=max(seg[idx*2].max,seg[idx*2+1].max);
}

node query(int L,int R,int l,int r,int idx)
{
  if(l>R || r<L)
  return {INF,0};

  if(L<=l && r<=R)
  return seg[idx];

  node p1=query(L,R,l,(l+r)/2,idx*2);
  node p2=query(L,R,(l+r)/2+1,r,idx*2+1);

  return {min(p1.min,p2.min),max(p1.max,p2.max)};
}

vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
  int Q = S.size();
  ll m=X.size();
  vector<vector<int>>g;
  g.assign(n,vector<int>());

  for(int i=0;i<m;i++)
  {
    g[X[i]].pb(Y[i]);
    g[Y[i]].pb(X[i]);
  }

  ll start=0;
  for(int i=0;i<n;i++)
  if(g[i].size()==1)
  {
    start=i;
    break;
  }

  ll dic[n];
  vector<int>ans;
    vector<bool>vis(n,0);
    queue<int>q;
    q.push(start);
    ll idx=0;
    vis[start]=1;
    while(!q.empty())
    {
      ll curr=q.front();
      dic[curr]=idx;
      arr[idx]=curr;
      idx++;
      q.pop();

      for(auto x:g[curr])
      if(!vis[x])
      {
        vis[x]=1;
        q.push(x);
      }
    }

  build(0,n-1,1);
  for(int i=0;i<Q;i++)
  {
      ll l=dic[S[i]],r=dic[E[i]];
      if(l<r)
      {
      bool tf=true;
      while(l<r)
      {
        ll mid=(l+r)/2;
        node left=query(l,mid,0,n-1,1);
        node right=query(mid+1,r,0,n-1,1);
        
        if(left.min<L[i] && right.max>R[i])
        {
          tf=0;
          break;
        }
        
        if(left.min<L[i])
        {
          r=mid;
          continue;
        }
          
        if(right.max>R[i])
        {
          l=mid+1;
          continue;
        }
        if(arr[mid]<=R[i] && arr[mid]>=L[i] || arr[mid+1]<=R[i] && arr[mid+1]>=L[i])
        break;
        else
        { 
          tf=0;
          break;
        }
      }
     
      ans.pb(tf);
      continue;
      }

      bool tf=true;
      swap(l,r);
      while(l<r)
      {
        ll mid=(l+r)/2;
        node left=query(l,mid,0,n-1,1);
        node right=query(mid+1,r,0,n-1,1);

        if(left.max>R[i] && right.min<L[i])
        {
          tf=0;
          break;
        }

        if(left.max>R[i])
        {
          r=mid;
          continue;
        }
          
        if(right.min<L[i])
        {
          l=mid+1;
          continue;
        }
          
        if(arr[mid]<=R[i] && arr[mid]>=L[i] || arr[mid+1]<=R[i] && arr[mid+1]>=L[i])
        break;
        else
        {
          tf=0;
          break;
        }
        }
        ans.pb(tf);
  }
  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:130:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  130 |         if(arr[mid]<=R[i] && arr[mid]>=L[i] || arr[mid+1]<=R[i] && arr[mid+1]>=L[i])
werewolf.cpp:169:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  169 |         if(arr[mid]<=R[i] && arr[mid]>=L[i] || arr[mid+1]<=R[i] && arr[mid+1]>=L[i])

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 314 ms 33168 KB Output is correct
2 Correct 333 ms 41516 KB Output is correct
3 Correct 358 ms 41496 KB Output is correct
4 Correct 669 ms 41524 KB Output is correct
5 Correct 810 ms 41696 KB Output is correct
6 Correct 727 ms 41504 KB Output is correct
7 Correct 449 ms 41596 KB Output is correct
8 Correct 326 ms 41516 KB Output is correct
9 Correct 286 ms 41620 KB Output is correct
10 Correct 420 ms 41464 KB Output is correct
11 Correct 612 ms 41516 KB Output is correct
12 Correct 450 ms 41520 KB Output is correct
13 Correct 398 ms 41540 KB Output is correct
14 Correct 396 ms 41548 KB Output is correct
15 Correct 423 ms 41820 KB Output is correct
16 Correct 415 ms 41600 KB Output is correct
17 Correct 523 ms 41596 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -