oj.uz

Submission #759304

# Submission time Handle Problem Language Result Execution time Memory
759304 2023-06-16T05:26:38 Z Khizri Werewolf (IOI18_werewolf) C++17
49 / 100
 1971 ms 38372 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=n;i>=1;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);
            }
        }
    }
    return ans;
}
/*
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
--
6 5 3
0 4
4 3
3 1
1 2
2 5
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: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++){
      |                 ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 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 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 197 ms 5360 KB Output is correct
11 Correct 111 ms 5348 KB Output is correct
12 Correct 16 ms 5460 KB Output is correct
13 Correct 215 ms 5364 KB Output is correct
14 Correct 125 ms 5332 KB Output is correct
15 Correct 182 ms 5484 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1604 ms 35892 KB Output is correct
2 Correct 1846 ms 35868 KB Output is correct
3 Correct 1933 ms 35852 KB Output is correct
4 Correct 1782 ms 35764 KB Output is correct
5 Correct 1748 ms 35916 KB Output is correct
6 Correct 1664 ms 35856 KB Output is correct
7 Correct 1971 ms 35844 KB Output is correct
8 Correct 1803 ms 35816 KB Output is correct
9 Correct 763 ms 35812 KB Output is correct
10 Correct 944 ms 35812 KB Output is correct
11 Correct 1075 ms 35956 KB Output is correct
12 Correct 1323 ms 35808 KB Output is correct
13 Correct 1790 ms 36088 KB Output is correct
14 Correct 1863 ms 35804 KB Output is correct
15 Correct 1824 ms 35784 KB Output is correct
16 Correct 1784 ms 35836 KB Output is correct
17 Correct 1873 ms 35844 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 197 ms 5360 KB Output is correct
11 Correct 111 ms 5348 KB Output is correct
12 Correct 16 ms 5460 KB Output is correct
13 Correct 215 ms 5364 KB Output is correct
14 Correct 125 ms 5332 KB Output is correct
15 Correct 182 ms 5484 KB Output is correct
16 Correct 1604 ms 35892 KB Output is correct
17 Correct 1846 ms 35868 KB Output is correct
18 Correct 1933 ms 35852 KB Output is correct
19 Correct 1782 ms 35764 KB Output is correct
20 Correct 1748 ms 35916 KB Output is correct
21 Correct 1664 ms 35856 KB Output is correct
22 Correct 1971 ms 35844 KB Output is correct
23 Correct 1803 ms 35816 KB Output is correct
24 Correct 763 ms 35812 KB Output is correct
25 Correct 944 ms 35812 KB Output is correct
26 Correct 1075 ms 35956 KB Output is correct
27 Correct 1323 ms 35808 KB Output is correct
28 Correct 1790 ms 36088 KB Output is correct
29 Correct 1863 ms 35804 KB Output is correct
30 Correct 1824 ms 35784 KB Output is correct
31 Correct 1784 ms 35836 KB Output is correct
32 Correct 1873 ms 35844 KB Output is correct
33 Incorrect 320 ms 38372 KB Output isn't correct
34 Halted 0 ms 0 KB -