제출 #431769

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
431769		Bench0310	Werewolf (IOI18_werewolf)	C++17	49 / 100	797 ms	96060 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;
typedef long long ll;

const int N=200005;
int n,q;
vector<int> v[N];

vector<int> solve_small(vector<int> ns,vector<int> ne,vector<int> nl,vector<int> nr)
{
    vector<int> res(q,0);
    for(int o=0;o<q;o++)
    {
        int s=ns[o];
        int e=ne[o];
        int l=nl[o];
        int r=nr[o];
        vector<array<int,2>> dp(n,{0,0});
        queue<array<int,2>> b;
        auto add=[&](int a,int t)
        {
            if(dp[a][t]==0)
            {
                dp[a][t]=1;
                b.push({a,t});
            }
        };
        add(s,0);
        while(!b.empty())
        {
            auto [a,t]=b.front();
            b.pop();
            if(l<=a&&a<=r&&t==0) add(a,1);
            for(int to:v[a])
            {
                if(t==0&&to>=l) add(to,0);
                if(t==1&&to<=r) add(to,1);
            }
        }
        res[o]=dp[e][1];
    }
    return res;
}

struct ST
{
    vector<int> tree;
    ST()
    {
        tree.assign(4*(n+5),0);
    }
    void update(int idx,int l,int r,int pos,int val)
    {
        if(l==r) tree[idx]=val;
        else
        {
            int m=(l+r)/2;
            if(pos<=m) update(2*idx,l,m,pos,val);
            else update(2*idx+1,m+1,r,pos,val);
            tree[idx]=tree[2*idx]+tree[2*idx+1];
        }
    }
    void upd(int pos,int val){update(1,0,n-1,pos,val);}
    int descend(int idx,int l,int r,int ql,int qr,int t) //0-l,1-r
    {
        if(ql>qr||tree[idx]==0) return -1;
        if(l==r) return l;
        int m=(l+r)/2;
        if(t==0)
        {
            int x=descend(2*idx,l,m,ql,min(qr,m),t);
            if(x!=-1) return x;
            else return descend(2*idx+1,m+1,r,max(ql,m+1),qr,t);
        }
        else
        {
            int x=descend(2*idx+1,m+1,r,max(ql,m+1),qr,t);
            if(x!=-1) return x;
            else return descend(2*idx,l,m,ql,min(qr,m),t);
        }
    }
    int dsn(int ql,int qr,int t){return descend(1,0,n-1,ql,qr,t);}
};

vector<int> tmpini(N,0);
vector<int> tree[4*N];

void build(int idx,int l,int r)
{
    if(l==r) tree[idx]={tmpini[l]};
    else
    {
        int m=(l+r)/2;
        build(2*idx,l,m);
        build(2*idx+1,m+1,r);
        tree[idx].reserve(r-l+1);
        merge(tree[2*idx].begin(),tree[2*idx].end(),tree[2*idx+1].begin(),tree[2*idx+1].end(),back_inserter(tree[idx]));
    }
}

bool query(int idx,int l,int r,int ql,int qr,int one,int two)
{
//    cout << "[" << idx << "," << l << "," << r << "," << ql << "," << qr << "," << one << "," << two << "]" << endl;
    if(ql>qr) return 0;
    if(l==ql&&r==qr)
    {
        auto it=lower_bound(tree[idx].begin(),tree[idx].end(),one);
        return (it!=tree[idx].end()&&(*it)<=two);
    }
    int m=(l+r)/2;
    return (query(2*idx,l,m,ql,min(qr,m),one,two)||query(2*idx+1,m+1,r,max(ql,m+1),qr,one,two));
}

vector<int> solve_line(vector<int> ns,vector<int> ne,vector<int> nl,vector<int> nr)
{
    vector<int> pos(n,-1);
    int src=-1;
    for(int i=0;i<n;i++) if(v[i].size()==1) src=i;
    int p=0;
    vector<int> h(n,-1);
    while(pos[src]==-1)
    {
//        cerr << src << " ";
        h[p]=src;
        pos[src]=p++;
        for(int to:v[src])
        {
            if(pos[to]==-1)
            {
                src=to;
                break;
            }
        }
    }
//    cerr << endl;
    tmpini=h;
    build(1,0,n-1);
    vector<int> badhuman(q,-1);
    vector<int> badwolf(q,-1);
    vector<int> ord[n];
    for(int i=0;i<q;i++)
    {
        int l=nl[i];
        ord[l].push_back(i);
    }
    ST one;
    for(int i=0;i<n;i++)
    {
        for(int a:ord[i])
        {
            int s=ns[a];
            int e=ne[a];
            if(pos[s]<pos[e]) badhuman[a]=one.dsn(pos[s],pos[e],0);
            else badhuman[a]=one.dsn(pos[e],pos[s],1);
        }
        one.upd(pos[i],1);
    }
    for(int i=0;i<n;i++) ord[i].clear();
    for(int i=0;i<q;i++)
    {
        int r=nr[i];
        ord[r].push_back(i);
    }
    ST two;
    for(int i=n-1;i>=0;i--)
    {
        for(int a:ord[i])
        {
            int s=ns[a];
            int e=ne[a];
            if(pos[s]<pos[e]) badwolf[a]=two.dsn(pos[s],pos[e],1);
            else badwolf[a]=two.dsn(pos[e],pos[s],0);
        }
        two.upd(pos[i],1);
    }
    vector<int> res(q,0);
    for(int i=0;i<q;i++)
    {
//        cerr << i << ": " << badhuman[i] << " " << badwolf[i] << endl;
        int l=nl[i];
        int r=nr[i];
        int s=ns[i];
        int e=ne[i];
        if(badhuman[i]==-1||badwolf[i]==-1) res[i]=1;
        else if(pos[s]<pos[e]) res[i]=(badwolf[i]<badhuman[i]&&query(1,0,n-1,badwolf[i]+1,badhuman[i]-1,l,r)==1);
        else res[i]=(badhuman[i]<badwolf[i]&&query(1,0,n-1,badhuman[i]+1,badwolf[i]-1,l,r)==1);
    }
    return res;
}

void ini(int nn,vector<int> nx,vector<int> ny,vector<int> ns)
{
    
    n=nn;
    int m=nx.size();
    q=ns.size();
    for(int i=0;i<m;i++)
    {
        v[nx[i]].push_back(ny[i]);
        v[ny[i]].push_back(nx[i]);
    }
}

void clean()
{
    for(int i=0;i<n;i++) v[i].clear();
    for(int i=0;i<4*(n+5);i++) tree[i].clear();
}

vector<int> check_validity(int nn,vector<int> nx,vector<int> ny,vector<int> ns,vector<int> ne,vector<int> nl,vector<int> nr)
{
    ini(nn,nx,ny,ns);
    int m=nx.size();
    if(n<=3000&&m<=6000&&q<=3000) return solve_small(ns,ne,nl,nr);
    else return solve_line(ns,ne,nl,nr);
}

//int main()
//{
//    mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
//    auto rng=[&](int l,int r)->int{return uniform_int_distribution<int>(l,r)(gen);};
//    auto rng_shuffle=[&](auto &t){shuffle(t.begin(),t.end(),gen);};
//    while(1)
//    {
//        n=rng(2,1000);
//        int m=n-1;
//        q=1000;
//        vector<int> x(m);
//        vector<int> y(m);
//        vector<int> ord(n);
//        for(int i=0;i<n;i++) ord[i]=i;
//        rng_shuffle(ord);
//        for(int i=0;i<n-1;i++)
//        {
//            x[i]=ord[i];
//            y[i]=ord[i+1];
//        }
//        vector<int> s(q);
//        vector<int> e(q);
//        vector<int> l(q);
//        vector<int> r(q);
//        for(int i=0;i<q;i++)
//        {
//            s[i]=rng(0,n-2);
//            e[i]=rng(s[i]+1,n-1);
//            l[i]=rng(0,s[i]);
//            r[i]=rng(e[i],n-1);
//        }
//        ini(n,x,y,s);
//        vector<int> one=solve_small(s,e,l,r);
//        vector<int> two=solve_line(s,e,l,r);
//        if(one!=two)
//        {
//            cout << "WA" << endl;
//            cout << n << " " << m << " " << q << endl;
//            for(int i=0;i<m;i++) cout << x[i] << " " << y[i] << endl;
//            for(int i=0;i<q;i++) cout << s[i] << " " << e[i] << " " << l[i] << " " << r[i] << endl;
//            cout << "|Received| ";
//            for(int i=0;i<q;i++) cout << two[i];
//            cout << endl;
//            cout << "|Expected| ";
//            for(int i=0;i<q;i++) cout << one[i];
//            cout << endl;
//            break;
//        }
//        else cout << "OK" << endl;
//        clean();
//    }
//    return 0;
//}

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