oj.uz

답안 #821680

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
821680 2023-08-11T13:00:38 Z Trumling 늑대인간 (IOI18_werewolf) C++14
0 / 100
 310 ms 41088 KB 
#include "werewolf.h"
#include <bits/stdc++.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;
};
vector<vector<int>>g;
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();
  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;
      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(dic[mid]<=R[i] && dic[mid]>=L[i] || dic[mid+1]<=R[i] && dic[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(dic[mid]<=R[i] && dic[mid]>=L[i] || dic[mid+1]<=R[i] && dic[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:126:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  126 |         if(dic[mid]<=R[i] && dic[mid]>=L[i] || dic[mid+1]<=R[i] && dic[mid+1]>=L[i])
werewolf.cpp:164:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  164 |         if(dic[mid]<=R[i] && dic[mid]>=L[i] || dic[mid+1]<=R[i] && dic[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
0 / 34.0

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

Subtask #4
0 / 51.0

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