Submission #1278396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278396		k12_khoi	Werewolf (IOI18_werewolf)	C++17	100 / 100	844 ms	148800 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second

const int N=4e5+5;
const int K=22;
const int oo=1e9+1;

int ori_n,ori_m,ori_request,n,m,request,x,y,u,v;
bool visited[N][2];
vector <int> Xvect,Yvect,Svect,Evect,Lvect,Rvect,adj[N],X,Y,S,E,L,R,ans;

namespace sub4
{
    int h,tour;
    int par[N][2],bit[N],arr[N][2],tin[N][2],tout[N][2],root[2],p[N][K][2];
    vector <int> adj[N][2],g[N];
    vector <pii> query[N];

    int acs(int u,int t)
    {
        if (par[u][t]<0) return u;
        return par[u][t]=acs(par[u][t],t);
    }

    void join(int u,int v,int t)
    {
        int x=acs(u,t);
        int y=acs(v,t);

        if (x!=y)
        {
            par[x][t]+=par[y][t];
            par[y][t]=x;

            root[t]=x;
            adj[x][t].push_back(y);
        }
    }

    void dfs(int u,int t)
    {
        tin[u][t]=++tour;
        arr[tour][t]=u;

        for (int v:adj[u][t])
        {
            p[v][0][t]=u;
            dfs(v,t);
        }

        tout[u][t]=tour;
    }

    void fenwick_update(int u,int v)
    {
        for (int idx=u;idx<=n;idx+=idx&-idx)
        bit[idx]+=v;
    }

    int fenwick_get(int u)
    {
        int ans=0;

        for (int idx=u;idx>0;idx-=idx&-idx)
        ans+=bit[idx];

        return ans;
    }

    void solve()
    {
        for (int i=0;i<m;i++)
        {
            X[i]++;
            Y[i]++;
        }

        for (int i=0;i<request;i++)
        {
            S[i]++;
            E[i]++;
            L[i]++;
            R[i]++;
        }

        for (int i=0;i<m;i++)
        {
            g[X[i]].push_back(Y[i]);
            g[Y[i]].push_back(X[i]);
        }


        for (int i=1;i<=n;i++)
        par[i][0]=par[i][1]=-1;


        for (int i=1;i<=n;i++)
        for (int j:g[i])
        if (i>j) join(i,j,0);

        for (int i=n;i>=1;i--)
        for (int j:g[i])
        if (i<j) join(i,j,1);

        tour=0;
        dfs(root[0],0);

        tour=0;
        dfs(root[1],1);


        h=31-__builtin_clz(n);

        for (int j=1;j<=h;j++)
        for (int i=1;i<=n;i++)
        {
            p[i][j][0]=p[p[i][j-1][0]][j-1][0];
            p[i][j][1]=p[p[i][j-1][1]][j-1][1];
        }

        for (int i=0;i<request;i++)
        {
            int l=L[i],r=R[i],s=S[i],e=E[i];

            for (int j=h;j>=0;j--)
            {
                if (p[s][j][1]>=l) s=p[s][j][1];
                if (p[e][j][0]<=r and p[e][j][0]!=0) e=p[e][j][0];
            }

            query[tout[e][0]].push_back(make_pair(i,1));
            query[tin[e][0]-1].push_back(make_pair(i,-1));

            L[i]=tin[s][1];
            R[i]=tout[s][1];
        }

        for (int i=1;i<=n;i++)
        {
            fenwick_update(tin[arr[i][0]][1],1);

            for (pii j:query[i])
            ans[j.X]+=(fenwick_get(R[j.X])-fenwick_get(L[j.X]-1))*j.Y;
        }

        for (int i=0;i<request;i++)
        ans[i]=(ans[i]>0);
    }
}

vector <int> check_validity(int originN,vector <int> originX,vector <int> originY,vector <int> originS,vector <int> originE,vector <int> originL,vector <int> originR)
{
    n=originN;
    m=originX.size();
    request=originS.size();

    X=originX;
    Y=originY;
    for (int i=0;i<m;i++)
    {
        x=X[i];
        y=Y[i];

        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    S=originS;
    E=originE;
    L=originL;
    R=originR;

    ans.resize(request);
    sub4::solve();

    return ans;
}

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