Submission #759303

#	Time	Username	Problem	Language	Result	Execution time	Memory
759303		Khizri	Werewolf (IOI18_werewolf)	C++17	34 / 100	1869 ms	83460 KiB

werewolf

#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 (stderr)

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: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51