Submission #733784

#	Time	Username	Problem	Language	Result	Execution time	Memory
733784		neki	Werewolf (IOI18_werewolf)	C++14	0 / 100	647 ms	96764 KiB

werewolf

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

using namespace std;

vc<int> check_validity(int n, vc<int> a, vc<int> b, vc<int> S, vc<int> E, vc<int> ql, vc<int> qr){
    int m=a.size(), Q=S.size();
    
    for(int i=0;i<m;++i)if(a[i]>b[i])swap(a[i],b[i]);
    vc<vc<int>> ledg(n), redg(n);for(int i=0;i<m;++i)ledg[b[i]].push_back(a[i]),redg[a[i]].push_back(b[i]);
    
    vc<vc<int>> lqs(n), rqs(n);for(int i=0;i<Q;++i)lqs[qr[i]].push_back(i),rqs[ql[i]].push_back(i);
    
    vc<int> ldsu(n),rdsu(n);for(int i=0;i<n;++i)ldsu[i]=i,rdsu[i]=i;
    function<int(int,vc<int>&)> fnd=[&fnd](int u,vc<int>& dsu){return (u==dsu[u])?u:dsu[u]=fnd(dsu[u],dsu);};
    vc<vc<int>> ltr(n),rtr(n);
    vc<int> lranno(Q),rranno(Q);
    for(int u=0;u<n;++u){
        for(auto v:ledg[u]){int pv=fnd(v,ldsu);if(pv!=u)ldsu[pv]=u,ltr[u].push_back(pv);}
        for(auto q:lqs[u])lranno[q]=fnd(E[q],ldsu);
    }
    for(int u=n-1;u>=0;--u){
        for(auto v:redg[u]){int pv=fnd(v,rdsu);if(pv!=u)rdsu[pv]=u,rtr[u].push_back(pv);}
        for(auto q:rqs[u])rranno[q]=fnd(S[q],rdsu);
    }
    
    function<void(int,int&,vc<vc<int>>&,vc<int>&,vc<int>&)> eul=[&eul](int u,int& T,vc<vc<int>>& tr,vc<int>& lran,vc<int>& rran){
        lran[u]=T++;
        for(auto v:tr[u])eul(v,T,tr,lran,rran);
        rran[u]=T;
    };
    int lT=0,rT=0;
    vc<int> lranx(n),rranx(n),lrany(n),rrany(n);
    for(int u=0;u<n;++u)if(u==ldsu[u])eul(u,lT,ltr,lranx,rranx);
    for(int u=n-1;u>=0;--u)if(u==rdsu[u])eul(u,rT,rtr,lrany,rrany);
    assert(lT==n&&rT==n);

    
    vc<array<int,3>> sw;
    for(int i=0;i<n;++i)sw.emplace_back(array<int,3>{lranx[i],0,lrany[i]});
    for(int i=0;i<Q;++i)sw.emplace_back(array<int,3>{lranx[lranno[i]],1,i});
    sort(sw.begin(),sw.end());
    
    vc<int> ans(Q,0);
    vc<vc<int>> sgtr(2*n);
    for(auto q:sw){
        if(q[1]==0){
            for(int y=q[2]+n;y>0;y>>=1){
                while(sgtr[y].size()){int i=sgtr[y].back();sgtr[y].pop_back();if(q[0]<rranx[lranno[i]])ans[i]=1;}
            }
        }
        if(q[1]==1){
            int i=q[2];
            for(int l=lrany[rranno[i]]+n, r=rrany[rranno[i]]+n;l<r;l>>=1,r>>=1){
                if(l&1)sgtr[l++].push_back(i);
                if(r&1)sgtr[--r].push_back(i);
            }
        }
    }
    return ans;
}

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