oj.uz

답안 #1006572

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1006572 2024-06-24T03:47:41 Z irmuun 늑대인간 (IOI18_werewolf) C++17
0 / 100
 1049 ms 524288 KB 
#include<bits/stdc++.h>
#include "werewolf.h"
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct segtreeMax{
    int n;
    vector<int>d;
    segtreeMax(int n):n(n){
        d.resize(4*n);
        build(1,0,n-1);
    }
    void build(int node,int l,int r){
        if(l==r){
            d[node]=0;
            return;
        }
        int mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
    }
    int query(int node,int l,int r,int L,int R){
        if(L>R||l>R||L>r) return 0;
        if(L<=l&&r<=R) return d[node];
        int mid=(l+r)/2;
        return max(query(node*2,l,mid,L,R),query(node*2+1,mid+1,r,L,R));
    }
    void update(int node,int l,int r,int pos,int val){
        if(r<pos||pos<l) return;
        if(l==r){
            d[node]=val;
            return;
        }
        int mid=(l+r)/2;
        update(node*2,l,mid,pos,val);
        update(node*2+1,mid+1,r,pos,val);
        d[node]=max(d[node*2],d[node*2+1]);
    }
};

struct segtreeMin{
    int n;
    vector<int>d;
    segtreeMin(int n):n(n){
        d.resize(4*n);
        build(1,0,n-1);
    }
    void build(int node,int l,int r){
        if(l==r){
            d[node]=0;
            return;
        }
        int mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
    }
    int query(int node,int l,int r,int L,int R){
        if(L>R||l>R||L>r) return n;
        if(L<=l&&r<=R) return d[node];
        int mid=(l+r)/2;
        return min(query(node*2,l,mid,L,R),query(node*2+1,mid+1,r,L,R));
    }
    void update(int node,int l,int r,int pos,int val){
        if(r<pos||pos<l) return;
        if(l==r){
            d[node]=val;
            return;
        }
        int mid=(l+r)/2;
        update(node*2,l,mid,pos,val);
        update(node*2+1,mid+1,r,pos,val);
        d[node]=min(d[node*2],d[node*2+1]);
    }
};
 
vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R){
    int Q=S.size();
    int n=N;
    vector<int>can(Q,0);
    vector<int>adj[N];
    for(int i=0;i<X.size();i++){
        adj[X[i]].pb(Y[i]);
        adj[Y[i]].pb(X[i]);
    }
    vector<int>pos(N);
    int cur=0;
    segtreeMax sgmx(N);
    segtreeMin sgmn(N);
    function <void(int,int)> dfs=[&](int x,int p){
        sgmx.update(1,0,n-1,cur,x);
        sgmn.update(1,0,n-1,cur,x);
        pos[x]=cur;
        cur++;
        for(int y:adj[x]){
            if(y!=p){
                dfs(y,x);
            }
        }
    };
    for(int i=0;i<N;i++){
        if(adj[i].size()==1){
            dfs(i,-1);
            break;
        }
    }
    for(int i=0;i<Q;i++){
        if(pos[E[i]]<=pos[S[i]]){
            int l=pos[E[i]],r=n-1,x,y;
            while(l<r){
                int mid=(l+r+1)/2;
                if(sgmn.query(1,0,n-1,pos[E[i]],mid)>=L[i]){
                    l=mid;
                }
                else{
                    r=mid-1;
                }
            }
            x=l;
            l=0,r=pos[S[i]];
            while(l<r){
                int mid=(l+r)/2;
                if(sgmx.query(1,0,n-1,mid,pos[S[i]])<=R[i]){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
            y=l;
            can[i]=(x>=y);
        }
        else{
            int l=pos[S[i]],r=n-1,x,y;
            while(l<r){
                int mid=(l+r+1)/2;
                if(sgmx.query(1,0,n-1,pos[S[i]],mid)<=R[i]){
                    l=mid;
                }
                else{
                    r=mid-1;
                }
            }
            x=l;
            l=0,r=pos[E[i]];
            while(l<r){
                int mid=(l+r)/2;
                if(sgmn.query(1,0,n-1,mid,pos[S[i]])>=L[i]){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
            y=l;
            can[i]=(x>=y);
        }
    }
    return can;
}

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:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i=0;i<X.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

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