Submission #359342

#	Time	Username	Problem	Language	Result	Execution time	Memory
359342		Rafi22	Werewolf (IOI18_werewolf)	C++14	49 / 100	809 ms	284044 KiB

werewolf

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

using namespace std;

#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
const int N=400007,M=600007,Q=400007;
vector<int> G[N];
vector<int> G1[N];
vector<int> DG[N+M];
int dsu[N];
vector<pair<int,int>>poc[N];
vector<pair<int,int>>kon[N];
int q[Q][2];
pair<int,int>seg[Q][2];

int Find(int v)
{
    if(v==dsu[v]) return v;
    return dsu[v]=Find(dsu[v]);
}
int it;
void Union(int u,int v)
{
   u=Find(u),v=Find(v);
   it++;
   dsu[it]=it;
   dsu[u]=it;
   dsu[v]=it;
   DG[it].pb(u);
   if(v!=u) DG[it].pb(v);
}

int pre[N+M],post[N+M],c;
int a1[N],a2[N];

void dfs(int v,bool b)
{
    if(sz(DG[v])==0)
    {
        pre[v]=++c;
        if(b) a2[c]=v;
        else a1[c]=v;
        post[v]=c;
    }
    else
    {
        pre[v]=inf;
        post[v]=0;
    }
    for(auto u:DG[v])
    {
        dfs(u,b);
        pre[v]=min(pre[v],pre[u]);
        post[v]=max(post[v],post[u]);
    }
}
int tree[4*N],pot=1;
vector<pair<pair<int,int>,pair<int,int>>>vec[N];
int que(int v,int a,int b,int l,int r)
{
    if(a<=l&&b>=r) return tree[v];
    if(l>b||r<a) return 0;
    return max(que(2*v,a,b,l,(l+r)/2),que(2*v+1,a,b,(l+r)/2+1,r));
}
void ins(int u,int v)
{
    int y=u+pot-1;
    tree[y]=v;
    while(y>1)
    {
        y/=2;
        tree[y]=max(tree[2*y],tree[2*y+1]);
    }
}


vector<int> check_validity(int n,vector<int> X,vector<int> Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R)
{
    for(int i=0;i<sz(X);i++)
    {
        X[i]++;
        Y[i]++;
        if(X[i]>Y[i])
        {
            G1[X[i]].pb(Y[i]);
            G[Y[i]].pb(X[i]);
        }
        else
        {
            G[X[i]].pb(Y[i]);
            G1[Y[i]].pb(X[i]);
        }
    }
    for(int i=0;i<sz(S);i++)
    {
        S[i]++;
        E[i]++;
        L[i]++;
        R[i]++;
        poc[L[i]].pb({S[i],i});
        kon[R[i]].pb({E[i],i});
    }
    it=n;
    for(int i=1;i<=n;i++) dsu[i]=i;
    for(int i=n;i>0;i--)
    {
        for(auto u:G[i]) Union(i,u);
        for(auto x:poc[i]) q[x.nd][0]=Find(x.st);
    }
    for(int i=1;i<=it;i++) if(Find(i)==i) dfs(i,0);
    for(int i=0;i<sz(S);i++) seg[i][0]={pre[q[i][0]],post[q[i][0]]};
    for(int i=1;i<=it;i++) DG[i].clear();
    it=n,c=0;
    for(int i=1;i<=n;i++) dsu[i]=i;
    for(int i=1;i<=n;i++)
    {
        for(auto u:G1[i]) Union(i,u);
        for(auto x:kon[i]) q[x.nd][1]=Find(x.st);
    }
    for(int i=1;i<=it;i++) if(Find(i)==i) dfs(i,1);
    for(int i=0;i<sz(S);i++) seg[i][1]={pre[q[i][1]],post[q[i][1]]};
    while(pot<n) pot*=2;
    for(int i=0;i<sz(S);i++)
    {
      //  cout<<seg[i][0].st<<" "<<seg[i][0].nd<<" "<<seg[i][1].st<<" "<<seg[i][1].nd<<endl;
        vec[seg[i][0].nd].pb({{seg[i][0].st,i},{seg[i][1].st,seg[i][1].nd}});
    }
    vector<int>ans(sz(S));
    for(int i=1;i<=n;i++)
    {
        ins(pre[a1[i]],i);
        for(auto x:vec[i])
        {
            //cout<<x.st.nd<<" "<<que(1,x.nd.st,x.nd.nd,1,pot)<<endl;
            if(que(1,x.nd.st,x.nd.nd,1,pot)>=x.st.st&&S[x.st.nd]>=L[x.st.nd]&&E[x.st.nd]<=R[x.st.nd]) ans[x.st.nd]=1;
        }
    }
    return ans;
}

/*int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int nn,mm,qq;
    cin>>nn>>mm>>qq;
    vector<int> xx(mm),yy(mm);
    for(int i=0;i<mm;i++) cin>>xx[i];
    for(int i=0;i<mm;i++) cin>>yy[i];
    vector<int> ss(qq),ee(qq),LL(qq),rr(qq);
    for(int i=0;i<qq;i++) cin>>ss[i];
    for(int i=0;i<qq;i++) cin>>ee[i];
    for(int i=0;i<qq;i++) cin>>LL[i];
    for(int i=0;i<qq;i++) cin>>rr[i];
    vector<int> veccc=check_validity(nn,xx,yy,ss,ee,LL,rr);
    for(auto x:veccc) cout<<x<<' ';

    return 0;
}*/

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