oj.uz

답안 #1013659

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1013659 2024-07-03T18:48:34 Z MarwenElarbi 늑대인간 (IOI18_werewolf) C++17
34 / 100
 2111 ms 259532 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=2e5+5;
vector<int> adj[nax];
int n;
int segtree[nax*4][2];
int tab[nax];
void build(int pos,int l,int r){
    if(l==r){
        segtree[pos][0]=segtree[pos][1]=tab[l];
        return;
    }
    int mid=(r+l)/2;
    build(pos*2+1,l,mid);
    build(pos*2+2,mid+1,r);
    segtree[pos][0]=min(segtree[pos*2+1][0],segtree[pos*2+2][0]);
    segtree[pos][1]=max(segtree[pos*2+1][1],segtree[pos*2+2][1]);
    return;
}
int query0(int pos,int l,int r,int left,int right){
    if(l>r||l>right||r<left) return 1e9;
    if(l>=left&&r<=right) return segtree[pos][0];
    int mid=(r+l)/2;
    return min(query0(pos*2+1,l,mid,left,right),query0(pos*2+2,mid+1,r,left,right));
}
int query1(int pos,int l,int r,int left,int right){
    if(l>r||l>right||r<left) return -1e9;
    if(l>=left&&r<=right) return segtree[pos][1];
    int mid=(r+l)/2;
    return max(query1(pos*2+1,l,mid,left,right),query1(pos*2+2,mid+1,r,left,right));
}
int bs_min_left(int x,int cur){
    int l=-1;
    int r=x;
    while(r-l>1){
        int mid=(r+l)/2;
        if (query0(0,0,n-1,mid,x)>=cur)
            r=mid;
        else l=mid;
    }
    return r;
}
int bs_min_right(int x,int cur){
    int l=x;
    int r=n;
    while(r-l>1){
        int mid=(r+l)/2;
        if (query0(0,0,n-1,x,mid)>=cur)
            l=mid;
        else r=mid;
    }
    return l;
}
int bs_max_left(int x,int cur){
    int l=-1;
    int r=x;
    while(r-l>1){
        int mid=(r+l)/2;
        if (query1(0,0,n-1,mid,x)<=cur)
            r=mid;
        else l=mid;
    }
    return r;
}
int bs_max_right(int x,int cur){
    int l=x;
    int r=n;
    while(r-l>1){
        int mid=(r+l)/2;
        if (query1(0,0,n-1,x,mid)<=cur)
            l=mid;
        else r=mid;
    }
    return l;
}
set<int> mergesort[nax*4];
void build_mergesort(int pos,int l,int r){
    if(l==r){
        mergesort[pos].insert(tab[l]);
        return;
    }
    int mid=(r+l)/2;
    build_mergesort(pos*2+1,l,mid);
    build_mergesort(pos*2+2,mid+1,r);
    for(auto u:mergesort[pos*2+1]) mergesort[pos].insert(u);
    for(auto u:mergesort[pos*2+2]) mergesort[pos].insert(u);
    return;
}
bool query(int pos,int l,int r,int left,int right,pair<int,int> cur){
    if(l>r||l>right||r<left) return 0;
    if(l>=left&&r<=right){
        return *mergesort[pos].lower_bound(cur.fi)<=cur.se;
    }
    int mid=(r+l)/2;
    return query(pos*2+1,l,mid,left,right,cur)|query(pos*2+2,mid+1,r,left,right,cur);
}
int t=0;
int conv[nax];
void dfs(int x,int p){
    conv[x]=t;
    tab[t++]=x;
    for(auto u:adj[x]){
        if(u==p) continue;
        dfs(u,x);
    }
    return;
}
std::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) {
    n=N;
    int q=R.size();
    int v[n];
    memset(v,0,sizeof v);
    for (int i = 0; i < n-1; ++i)
    {
        adj[X[i]].pb(Y[i]);
        adj[Y[i]].pb(X[i]);
        v[X[i]]++;
        v[Y[i]]++;
    }
    int lst;
    for (int i = 0; i < n; ++i)
    {
        if(v[i]==1){
            lst=i;
        }
    }
    dfs(lst,-1);
    build(0,0,n-1);
    build_mergesort(0,0,n-1);
    vector<int> ans;
    for (int i = 0; i < q; ++i)
    {
        pair<int,int> cur={L[i],R[i]};
        S[i]=conv[S[i]];
        E[i]=conv[E[i]];
        bool test=(E[i]>=S[i]);
        pair<int,int> cnt;
        if(test){
            int right=bs_min_right(S[i],cur.fi);
            int left=bs_max_left(E[i],cur.se);
            cnt={right,left};
        }else{
            int right=bs_min_left(S[i],cur.fi);
            int left=bs_max_right(E[i],cur.se);
            cnt={left,right};
        } 
       
        if(cnt.fi<cnt.se){
            ans.pb(0);
            continue;
        }
        ans.pb((query(0,0,n-1,cnt.se,cnt.fi,cur)) ? 1 : 0);
    }
    return ans;
}

/*namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
  int N = read_int();
  int M = read_int();
  int Q = read_int();
  std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
  for (int j = 0; j < M; ++j) {
    X[j] = read_int();
    Y[j] = read_int();
  }
  for (int i = 0; i < Q; ++i) {
    S[i] = read_int();
    E[i] = read_int();
    L[i] = read_int();
    R[i] = read_int();
  }

  std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
  for (size_t i = 0; i < A.size(); ++i) {
    printf("%d\n", A[i]);
  }
  return 0;
}*/

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:135:8: warning: 'lst' may be used uninitialized in this function [-Wmaybe-uninitialized]
  135 |     dfs(lst,-1);
      |     ~~~^~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 141 ms 237320 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 141 ms 237320 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1658 ms 259044 KB Output is correct
2 Correct 2111 ms 259312 KB Output is correct
3 Correct 2001 ms 259276 KB Output is correct
4 Correct 2012 ms 259292 KB Output is correct
5 Correct 2009 ms 259424 KB Output is correct
6 Correct 1920 ms 259388 KB Output is correct
7 Correct 1719 ms 259384 KB Output is correct
8 Correct 1999 ms 259532 KB Output is correct
9 Correct 1333 ms 259376 KB Output is correct
10 Correct 1501 ms 259292 KB Output is correct
11 Correct 1561 ms 259232 KB Output is correct
12 Correct 1536 ms 259328 KB Output is correct
13 Correct 2015 ms 259292 KB Output is correct
14 Correct 2043 ms 259216 KB Output is correct
15 Correct 1975 ms 259292 KB Output is correct
16 Correct 1906 ms 259300 KB Output is correct
17 Correct 1726 ms 259276 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 141 ms 237320 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -