oj.uz

Submission #1006574

# Submission time Handle Problem Language Result Execution time Memory
1006574 2024-06-24T03:53:43 Z irmuun Werewolf (IOI18_werewolf) C++17
34 / 100
 1349 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[S[i]]<=pos[E[i]]){
            int l=pos[S[i]],r=n-1,x,y;
            while(l<r){
                int mid=(l+r+1)/2;
                if(sgmn.query(1,0,n-1,pos[S[i]],mid)>=L[i]){
                    l=mid;
                }
                else{
                    r=mid-1;
                }
            }
            x=l;
            l=0,r=pos[E[i]];
            while(l<r){
                int mid=(l+r)/2;
                if(sgmx.query(1,0,n-1,mid,pos[E[i]])<=R[i]){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
            y=l;
            can[i]=(x>=y);
        }
        else{
            int l=pos[E[i]],r=n-1,x,y;
            while(l<r){
                int mid=(l+r+1)/2;
                if(sgmx.query(1,0,n-1,pos[E[i]],mid)<=R[i]){
                    l=mid;
                }
                else{
                    r=mid-1;
                }
            }
            x=l;
            l=0,r=pos[S[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

# Verdict Execution time Memory Grader output
1 Runtime error 237 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 237 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1202 ms 47372 KB Output is correct
2 Correct 1287 ms 55680 KB Output is correct
3 Correct 1349 ms 55696 KB Output is correct
4 Correct 1309 ms 55852 KB Output is correct
5 Correct 1302 ms 55820 KB Output is correct
6 Correct 1243 ms 55848 KB Output is correct
7 Correct 1216 ms 55856 KB Output is correct
8 Correct 1224 ms 55636 KB Output is correct
9 Correct 689 ms 55636 KB Output is correct
10 Correct 913 ms 55636 KB Output is correct
11 Correct 943 ms 55636 KB Output is correct
12 Correct 789 ms 55636 KB Output is correct
13 Correct 1215 ms 55848 KB Output is correct
14 Correct 1218 ms 55816 KB Output is correct
15 Correct 1215 ms 55852 KB Output is correct
16 Correct 1241 ms 55636 KB Output is correct
17 Correct 1272 ms 55908 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 237 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -