oj.uz

Submission #759302

# Submission time Handle Problem Language Result Execution time Memory
759302 2023-06-16T05:15:17 Z Khizri Werewolf (IOI18_werewolf) C++17
15 / 100
 1537 ms 71968 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(l>qr||r<ql){
        pii ans;
        ans.F=n+5;
        ans.S=-5;
        return ans;
    }
    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);
    //cout<<1<<endl;
    for(int i=1;i<=q;i++){
        int s=idx[x[i]],e=idx[y[i]];
        //cout<<s<<' '<<e<<endl;
        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;
            //cout<<pos<<' '<<pos2<<endl;
            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;
            //cout<<pos<<' '<<pos2<<endl;
            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
-------
5 4 1
0 1
1 2
2 3
3 4
1 3 1 2
*/

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5008 KB Output is correct
3 Correct 3 ms 5012 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 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 4948 KB Output is correct
2 Correct 3 ms 5008 KB Output is correct
3 Correct 3 ms 5012 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 186 ms 5396 KB Output is correct
11 Correct 106 ms 5568 KB Output is correct
12 Correct 14 ms 5588 KB Output is correct
13 Correct 211 ms 5488 KB Output is correct
14 Correct 125 ms 5428 KB Output is correct
15 Correct 185 ms 5604 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 1537 ms 71968 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5008 KB Output is correct
3 Correct 3 ms 5012 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 186 ms 5396 KB Output is correct
11 Correct 106 ms 5568 KB Output is correct
12 Correct 14 ms 5588 KB Output is correct
13 Correct 211 ms 5488 KB Output is correct
14 Correct 125 ms 5428 KB Output is correct
15 Correct 185 ms 5604 KB Output is correct
16 Runtime error 1537 ms 71968 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -