oj.uz

Submission #759298

# Submission time Handle Problem Language Result Execution time Memory
759298 2023-06-16T04:57:39 Z Khizri Werewolf (IOI18_werewolf) C++17
15 / 100
 450 ms 524288 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e5+5;
int n,q,m,x[mxn],y[mxn],a[mxn],b[mxn],color[3005],color2[3005],idx[mxn],arr[mxn];
pii tree[4*mxn];
vector<int>vt[mxn];
void build(int node,int l,int r){
    if(l==r){
        tree[node].F=arr[l];
        tree[node].S=arr[l];
        return;
    }
    int m=(l+r)/2;
    build(2*node,l,m);
    build(2*node+1,m+1,r);
    tree[node].F=min(tree[2*node].F,tree[2*node+1].F);
    tree[node].S=max(tree[2*node].S,tree[2*node+1].S);
}
pii query(int node,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return tree[node];
    int m=(l+r)/2;
    pii x=query(2*node,l,m,ql,qr);
    pii y=query(2*node+1,m+1,r,ql,qr);
    pii ans;
    ans.F=min(x.F,y.F);
    ans.S=max(x.S,y.S);
    return ans;
}
void dfs(int u,int l,int r){
    if(u<l||u>r) return;
    color[u]=1;
    for(int v:vt[u]){
        if(!color[v]&&v>=l&&v<=r){
            dfs(v,l,r);
        }
    }
}
void dfs2(int u,int l,int r){
    if(u<l||u>r) return;
    color2[u]=1;
    for(int v:vt[u]){
        if(!color2[v]&&v>=l&&v<=r){
            dfs2(v,l,r);
        }
    }
}
void give_idx(int u,int p,int id){
    idx[u]=id;
    arr[id]=u;
    for(int v:vt[u]){
        if(v!=p){
            give_idx(v,u,id+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) {
    n=N;
    m=X.size();
    q=S.size();
    for(int i=0;i<X.size();i++){
        vt[X[i]+1].pb(Y[i]+1);
        vt[Y[i]+1].pb(X[i]+1);
    }
    for(int i=0;i<S.size();i++){
        x[i+1]=S[i]+1;
        y[i+1]=E[i]+1;
        a[i+1]=L[i]+1;
        b[i+1]=R[i]+1;
    }
    vector<int>ans;
    if(n<=3000&&m<=6000&&q<=3000){
        for(int i=1;i<=q;i++){
            memset(color,0,sizeof(color));
            memset(color2,0,sizeof(color2));
            dfs(x[i],a[i],n);
            dfs2(y[i],1,b[i]);
            int ok=0;
            for(int j=a[i];j<=b[i];j++){
                if(color[j]&&color2[j]){
                    ok=1;
                    break;
                }
            }
            if(ok){
                ans.pb(1);
            }
            else{
                ans.pb(0);
            }
        }
        return ans;
    }
    int st=0;
    for(int i=1;i<=n;i++){
        if(vt[i].size()==1){
            st=i;
            break;
        }
    }
    give_idx(st,-1,1);
    build(1,1,n);
    for(int i=1;i<=q;i++){
        int s=idx[x[i]],e=idx[y[i]];
        int p=0;
        if(s>e){
            swap(s,e);
            p=1;
        }
        if(!p){
            int l=s,r=e;
            while(l<=r){
                int m=(l+r)/2;
                if(query(1,1,n,s,m).F>=a[i]){
                    l=m+1;
                }
                else{
                    r=m-1;
                }
            }
            int pos=l-1;
            l=s,r=e;
            while(l<=r){
                int m=(l+r)/2;
                if(query(1,1,n,m,e).S<=b[i]){
                    r=m-1;
                }
                else{
                    l=m+1;
                }
            }
            int pos2=r+1;
            if(pos2<=pos){
                ans.pb(1);
            }
            else{
                ans.pb(0);
            }
        }
        else{
            int l=s,r=e;
            while(l<=r){
                int m=(l+r)/2;
                if(query(1,1,n,s,m).S<=b[i]){
                    l=m+1;
                }
                else{
                    r=m-1;
                }
            }
            int pos=l-1;
            l=s,r=e;
            while(l<=r){
                int m=(l+r)/2;
                if(query(1,1,n,m,e).F>=a[i]){
                    r=m-1;
                }
                else{
                    l=m+1;
                }
            }
            int pos2=r+1;
            if(pos2<=pos){
                ans.pb(1);
            }
            else{
                ans.pb(0);
            }
        }
    }
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

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:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i=0;i<X.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i=0;i<S.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:184:1: warning: control reaches end of non-void function [-Wreturn-type]
  184 | }
      | ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5012 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 4 ms 5008 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5012 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 4 ms 5008 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 195 ms 5468 KB Output is correct
11 Correct 112 ms 5420 KB Output is correct
12 Correct 15 ms 5584 KB Output is correct
13 Correct 210 ms 5400 KB Output is correct
14 Correct 126 ms 5404 KB Output is correct
15 Correct 193 ms 5632 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5012 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 4 ms 5008 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 195 ms 5468 KB Output is correct
11 Correct 112 ms 5420 KB Output is correct
12 Correct 15 ms 5584 KB Output is correct
13 Correct 210 ms 5400 KB Output is correct
14 Correct 126 ms 5404 KB Output is correct
15 Correct 193 ms 5632 KB Output is correct
16 Runtime error 450 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -