Submission #261879

#	Time	Username	Problem	Language	Result	Execution time	Memory
261879		yabsed	Werewolf (IOI18_werewolf)	C++17	15 / 100	4054 ms	29804 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
int ok[3][200555];
vector <int> v[200555];
vector <int> new_old;
int old_new[200555];
int f(int N, int s, int e, int l, int r){
    queue <int> q;
    memset(ok, 0, sizeof(ok));

    if(l<=s){
        ok[1][s]=1;
        q.push(1);
        q.push(s);
    }
    if(e<=r){
        ok[0][e]=1;
        q.push(0);
        q.push(e);
    }
    while(!q.empty()){
        int type=q.front(); q.pop();
        int x=q.front(); q.pop();
        //rintf("%d %d\n", type, x);
        for(int i=0;i<v[x].size();i++){
            if(type==0){
                if(v[x][i]<=r&&ok[type][v[x][i]]==0){
                    ok[type][v[x][i]]=1;
                    q.push(type);
                    q.push(v[x][i]);
                }
            }
            else{
                if(l<=v[x][i]&&ok[type][v[x][i]]==0){
                    ok[type][v[x][i]]=1;
                    q.push(type);
                    q.push(v[x][i]);
                }
            }
        }
    }
    for(int i=0;i<N;i++)
        if(ok[0][i]&&ok[1][i])return 1;
    return 0;
}
int nn;
int dp_min[600555];
int dp_max[600555];
void Cal_DP(int N){
    for(nn=1;nn<N;nn*=2);
    for(int i=nn;i<2*nn;i++){
        dp_min[i]=N+5;
        dp_max[i]=-1;
        if(i-nn<N)dp_min[i]=dp_max[i]=new_old[i-nn];
    }
    for(int i=nn-1;i;i--){
        dp_min[i]=min(dp_min[2*i], dp_min[2*i+1]);
        dp_max[i]=max(dp_max[2*i], dp_max[2*i+1]);
    }
}
void Apple(int N){
    int vis[200555];
    memset(vis, 0, sizeof(vis));

    int start;
    for(start=0;start<N;start++)
        if(v[start].size()==1)
            break;

    for(int i=0;i<=N;i++){
        vis[start]=1;
        new_old.push_back(start);
        old_new[start]=i;
        for(int j=0;j<v[start].size();j++)
            if(!vis[j])
                start=j;
    }
}
int find_min(int i, int c_l, int c_r, int input_l, int input_r){
    if(input_l<=c_l&&c_r<=input_r)return dp_min[i];
    if(input_r<c_l||c_r<input_l)return 987654321;
    int res=987654321;
    int mid=(c_l+c_r)/2;
    if(input_l<=c_r)res=min(res, f(2*i, c_l, mid, input_l, input_r));
    if(c_l<=input_r)res=min(res, f(2*i+1, mid+1, c_r, input_l, input_r));
    return res;
}
int find_max(int i, int c_l, int c_r, int input_l, int input_r){
    if(input_l<=c_l&&c_r<=input_r)return dp_max[i];
    if(input_r<c_l||c_r<input_l)return -1;
    int res=-1;
    int mid=(c_l+c_r)/2;
    if(input_l<=c_r)res=max(res, f(2*i, c_l, mid, input_l, input_r));
    if(c_l<=input_r)res=max(res, f(2*i+1, mid+1, c_r, input_l, input_r));
    return res;
}
int g(int N, int s, int e, int l, int r){
    if(s<l)return 0;
    if(r<e)return 0;
    int l1=old_new[s], r1=N-1, man_max=old_new[s];
    while(l1<=r1){
        int mid=(l1+r1)/2;
        int z=find_min(1, 1, nn, old_new[s]+1, mid+1);
        if(l<=z)man_max=max(man_max, mid), l1=mid+1;
        else r1=mid-1;
    }
    int l2=0, r2=old_new[s], man_min=old_new[s];
    while(l2<=r2){
        int mid=(l2+r2)/2;
        int z=find_min(1, 1, nn, mid+1, old_new[s]+1);
        if(l<=z)man_min=max(man_min, mid), r2=mid-1;
        else l2=mid+1;
    }
    int f1=man_min, f2=man_max;

    l1=old_new[e], r1=N-1, man_max=old_new[e];
    while(l1<=r1){
        int mid=(l1+r1)/2;
        int z=find_max(1, 1, nn, old_new[e]+1, mid+1);
        if(r>=z)man_max=max(man_max, mid), l1=mid+1;
        else r1=mid-1;
    }
    l2=0, r2=old_new[e], man_min=old_new[e];
    while(l2<=r2){
        int mid=(l2+r2)/2;
        int z=find_min(1, 1, nn, mid+1, old_new[e]+1);
        if(r>=z)man_min=max(man_min, mid), r2=mid-1;
        else l2=mid+1;
    }
    int f3=man_min, f4=man_max;
    if(f4<f1||f2<f3)return 0;
    return 1;
}
vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    int Q = S.size();
    for(int i=0;i<X.size();i++){
        v[X[i]].push_back(Y[i]);
        v[Y[i]].push_back(X[i]);
    }
    vector<int> A(Q);
    if(N<=3000&&X.size()<=6000&Q<=3000){
        for (int i = 0; i < Q; ++i)
            A[i] = f(N, S[i], E[i], L[i], R[i]);
        return A;
    }

    Apple(N);
    Cal_DP(N);
    for(int i=0;i<Q;i++){
        A[i]=g(N, S[i], E[i], L[i], R[i]);
    }
    return A;

}

Compilation message (stderr)

werewolf.cpp: In function 'int f(int, int, int, int, int)':
werewolf.cpp:26:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<v[x].size();i++){
                     ~^~~~~~~~~~~~
werewolf.cpp: In function 'void Apple(int)':
werewolf.cpp:75:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<v[start].size();j++)
                     ~^~~~~~~~~~~~~~~~
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:139:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<X.size();i++){
                 ~^~~~~~~~~
werewolf.cpp:144:25: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
     if(N<=3000&&X.size()<=6000&Q<=3000){
                 ~~~~~~~~^~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51