Submission #142809

#	Time	Username	Problem	Language	Result	Execution time	Memory
142809		LittleFlowers__	Werewolf (IOI18_werewolf)	C++14	0 / 100	1316 ms	524288 KiB

werewolf

#include <bits/stdc++.h>
//#include "werewolf.h"
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(false),cin.tie(nullptr);
#define task "werewolf"
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))

int pos[100010],lz[100010];
int mn[100010][20],mx[100010][20];
vector<int> ad[100010];

int gmin(int i,int j){
    int t=lz[j-i+1];
    return min(mn[i][t],mn[j-(1<<t)+1][t]);
}
int gmax(int i,int j){
    int t=lz[j-i+1];
    return max(mx[i][t],mx[j-(1<<t)+1][t]);
}


vector<int> check_validity(int n, vector<int>x, vector<int>y, vector<int>s, vector<int>t, vector<int>l, vector<int>r){
    forinc(i,1,n) lz[i]=log2(i);
    forinc(i,0,x.size()-1){
        ad[x[i]].pb(y[i]);
        ad[y[i]].pb(x[i]);
    }
    int st=0,pr=0; while(ad[st].size()>1) st++;
    vector<int> a;
    for(;;){
        int ok=0;
        a.pb(st); pos[st]=a.size();
        forv(v,ad[st]) if(v!=pr){
            ok=1;
            pr=st;
            st=v;
        }
        if(!ok) break;
    }
    forinc(i,1,n) mn[i][0]=mx[i][0]=a[i-1];
    forinc(j,1,18) forinc(i,1,n){
        if(i+(1<<j)>n+1) break;
        mx[i][j]=max(mx[i][j-1],mx[i+(1<<j-1)][j-1]);
        mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);
    }
    vector<int> ret;
    forinc(i,0,l.size()-1){
        if(s[i]<l[i] || t[i]>r[i]){
            ret.pb(0);
            continue;
        }
        int st=s[i],ed=t[i];
        int le,ri,X,Y;
        if(pos[st]<=pos[ed]){
            le=st,ri=ed;
            while(le<=ri){
                int mi=(le+ri)/2;
                if(gmin(le,mi)>=l[i]) X=mi,le=mi+1;
                else ri=mi-1;
            }
            le=st,ri=ed;
            while(le<=ri){
                int mi=(le+ri)/2;
                if(gmax(mi,ri)<=r[i]) Y=mi,ri=mi-1;
                else le=mi+1;
            }
        } else{
            le=ed,ri=st;
            while(le<=ri){
                int mi=(le+ri)/2;
                if(gmax(le,mi)<=r[i]) X=mi,le=mi+1;
                else ri=mi-1;
            }
            le=ed,ri=st;
            while(le<=ri){
                int mi=(le+ri)/2;
                if(gmin(mi,ri)>=l[i]) Y=mi,ri=mi-1;
                else le=mi+1;
            }
        }
        ret.pb(X>=Y);
    }
    return ret;
}

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:58:43: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
         mx[i][j]=max(mx[i][j-1],mx[i+(1<<j-1)][j-1]);
                                          ~^~
werewolf.cpp:59:43: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
         mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);
                                          ~^~
werewolf.cpp:96:17: warning: 'Y' may be used uninitialized in this function [-Wmaybe-uninitialized]
         ret.pb(X>=Y);
                ~^~~
werewolf.cpp:96:17: warning: 'X' may be used uninitialized in this function [-Wmaybe-uninitialized]

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