Submission #1045532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045532		SiliconSquared	Werewolf (IOI18_werewolf)	C++14	15 / 100	165 ms	84232 KiB

werewolf

#include "werewolf.h"
using namespace std;
#include <vector>
#include <cmath>
#define INF 999999999
struct node{
    int x;
    vector<int> v;
    bool g,h;
    node(){}
};
vector<node> v;
std::vector<int> sub1(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) {
    v.resize(n);
    for (int i=0;i<X.size();i++){
        v[X[i]].v.push_back(Y[i]);
        v[Y[i]].v.push_back(X[i]);
    }
    vector<int> q;
    vector<int> z;
    z.resize(S.size());
    int p;
    bool f;
    for (int _=0;_<S.size();_++){
        for (int i=0;i<n;i++){v[i].g=false;v[i].h=false;}
        q.clear();
        q.push_back(S[_]);
        f=false;
        while (!q.empty()){
            p=q[q.size()-1];
            q.pop_back();
            if (v[p].g||p<L[_]){continue;}
            v[p].g=true;
            for (int i:v[p].v){
                q.push_back(i);
            }
        }
        q.clear();
        q.push_back(E[_]);
        while (!q.empty()){
            p=q[q.size()-1];
            q.pop_back();
            if (v[p].h||p>R[_]){continue;}
            if (v[p].g){f=true;break;}
            v[p].h=true;
            for (int i:v[p].v){
                q.push_back(i);
            }
        }
        z[_]=f;
    }
    return z;
}
struct seg{
    int s,x,y,z;
    seg(){}
    seg(int _x,int _z){
        s=INF;x=_x;z=_z;y=(x+z)/2;
    }
};
struct segtree{
    int n;
    vector<seg> v;
    segtree(){}
    segtree(int _n){
        n=pow(2,ceil(log2(_n)));
        v.resize(n*2);
        v[1]=seg(0,n);
        for (int i=2;i<n*2;i++){
            if (i%2==0){v[i]=seg(v[i/2].x,v[i/2].y);}
            else{v[i]=seg(v[i/2].y,v[i/2].z);}
        }
    }
    void update(int i,int s){
        i+=n;
        v[i].s=s;
        while (i!=1){
            i/=2;
            v[i].s=min(v[i*2].s,v[i*2+1].s);
        }
    }
    int query(int a,int b,int i){
        if (a>=b){return INF;}
        if (a==v[i].x&&b==v[i].z){return v[i].s;}
        return min(query(a,min(b,v[i].y),i*2),query(max(a,v[i].y),b,i*2+1));
    }
    int walk(int a,int s){
        int i=a+n;
        if (v[i].s<s){return a;}
        if (v[1].s>=s){return INF;}
        i/=2;
        while (v[i*2+1].s>=s){
            i/=2;
        }
        while (v[i].x+1!=v[i].z){
            if (v[i*2].s<s){
                i*=2;
            }else{
                i=i*2+1;
            }
        }
        return i-n;
    }
};
std::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) {
    if (n<=3000 && X.size()<=6000 and S.size()<=3000){return sub1(n,X,Y,S,E,L,R);}
    vector<int> w;
    vector<int> m;
    vector<vector<int>> raw;
    raw.resize(n);
    for (int i=0;i<n-1;i++){
        raw[X[i]].push_back(Y[i]);
        raw[Y[i]].push_back(X[i]);
    }
    int x,y;
    for (int i=0;i<n;i++){
        if (raw[i].size()==1){x=i;break;}
    }
    y=-1;
    for (int i=0;i<n-1;i++){
        w.push_back(x);
        if (raw[x][0]==y){y=x;x=raw[x][1];}
        else{y=x;x=raw[x][0];}
    }
    w.push_back(x);
    segtree pos=segtree(n);//search for max, walk to next thing smaller than s
    segtree neg=segtree(n);
    m.resize(n);
    for (int i=0;i<n;i++){
        pos.update(i,w[i]);
        neg.update(i,-w[i]);
        m[w[i]]=i;
    }
    int a,b,l,r;
    bool f;
    vector<int> z;
    for (int i=0;i<S.size();i++){
        a=S[i];b=E[i];l=L[i];r=R[i];
        f=true;
        if (m[a]<m[b]){
            a=pos.walk(a,l);
            b=m[b];
            if (a>b){a=b;}
            if (w[a-1]>r){f=false;}
            if (neg.query(a,b,1)<-r){f=false;}
        }else{
            a=m[a];
            b=neg.walk(b,-r);
            if (b>a){a=b;}
            if (w[b-1]<l){f=false;}
            if (pos.query(b,a,1)<l){f=false;}
        }
        z.push_back(f);
    }
    return z;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> sub1(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:15:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (int i=0;i<X.size();i++){
      |                  ~^~~~~~~~~
werewolf.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int _=0;_<S.size();_++){
      |                  ~^~~~~~~~~
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:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for (int i=0;i<S.size();i++){
      |                  ~^~~~~~~~~

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