Submission #519878

#	Time	Username	Problem	Language	Result	Execution time	Memory
519878		oneloveforever	Werewolf (IOI18_werewolf)	C++14	7 / 100	4083 ms	524292 KiB

werewolf

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define x first
#define y second
#define ii pair<int,int>
const int M=3e5+7;
const int LOG=20;
int n;
int trace[M][LOG+10][2],beg[M][2],fin[M][2],id[M][2],pre[2];
struct DSU
{
    int n;
    vector<vector<int> >trace;
    DSU(int _n=0)
    {
        n=_n;
        trace.resize(2,vector<int>(n+7));
        for(int need=0;need<=1;need++)
        {
            iota(trace[need].begin(),trace[need].end(),0);
        }
    }
    int get(int x,int index)
    {
        return trace[index][x]==x?trace[index][x]:trace[index][x]=get(trace[index][x],index);
    }
    void conncet(int x,int y,int index,vector<vector<int> >&adj)
    {
        int u=get(x,index);
        int v=get(y,index);
        if(u==v)return ;
        trace[index][v]=u;
        adj[u].push_back(v);
    }
};
void dfs(int x,int cha,int index,vector<vector<int> >adj)
{
    pre[index]++;
    beg[x][index]=pre[index];
    id[pre[index]][index]=x;
    for(int node:adj[x])
    {
        if(node==cha)continue;
        trace[node][0][index]=x;
        dfs(node,x,index,adj);
    }
    fin[x][index]=pre[index];
}
void sprase()
{
    for(int index=0;index<=1;index++)
    {
        for(int i=1;i<=LOG;i++)
        {
            for(int node=1;node<=n;node++)
            {
                if(trace[node][i-1][index]!=-1)
                {
                    trace[node][i][index]=trace[trace[node][i-1][index]][i-1][index];
                }
            }
        }
    }
}
struct node
{
    int x,y,value,id;
    node(int _x=0,int _y=0,int _value=0,int _id=0)
    {
        x=_x,y=_y,value=_value,id=_id;
    }
};
struct IT
{
    int n;
    vector<int>bit;
    IT(int _n=0)
    {
        n=_n;
        bit.assign(n+7,0);
    }
    void update(int x,int value)
    {
        for(;x<=n;x+=x&(-x))
        {
            bit[x]+=value;
        }
    }
    int get(int x)
    {
        int ans=0;
        for(;x;x-=x&(-x))
        {
            ans+=bit[x];
        }
        return ans;
    }
    int get_sum(int x,int y)
    {
        return get(y)-get(x-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)
{
    memset(trace,-1,sizeof(trace));
    n=N;
    vector<vector<int> >a(n+7);
    for(int i=1;i<=(int)X.size();i++)
    {
        int x=X[i-1]+1;
        int y=Y[i-1]+1;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    vector<vector<int> >minv(n+1);
    vector<vector<int> >maxv(n+1);
    DSU s(n);
    for(int i=1;i<=n;i++)
    {
        for(int node:a[i])if(node<i)
        {
            s.conncet(i,node,0,maxv);
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int node:a[i])if(node>i)
        {
            s.conncet(i,node,1,minv);
        }
    }
    dfs(1,0,0,minv);
    dfs(n,0,1,maxv);
    sprase();
    int q=(int)L.size();
    vector<ii>place(q+1);
    for(int i=1;i<=q;i++)
    {
        int x=L[i-1]+1;
        int y=R[i-1]+1;
        place[i]=make_pair(x,y);
    }
    vector<vector<node> >query(n+1);
    for(int i=1;i<=q;i++)
    {
        int x=S[i-1]+1;
        int y=E[i-1]+1;
        for(int node=LOG;node>=0;node--)
        {
            if(trace[x][node][0]==-1)continue;
            if(trace[x][node][0]>=place[i].x)x=trace[x][node][0];
        }
        for(int node=LOG;node>=0;node--)
        {
            if(trace[y][node][1]==-1)continue;
            if(trace[y][node][1]<=place[i].y)y=trace[y][node][1];
        }
        int node_x=beg[x][0]-1;
        int node_y=fin[x][0];
        query[node_x].push_back({beg[y][1],fin[y][1],-1,i});
        query[node_y].push_back({beg[y][1],fin[y][1],1,i});
    }
    IT bit(n);
    vector<int>ans(q+1);
    for(int i=0;i<=n;i++)
    {
        if(i>0)
        {
            int new_node=beg[id[i][0]][1];
            bit.update(new_node,1);
        }
        for(node need:query[i])
        {
            ans[need.id]+=need.value*bit.get_sum(need.x,need.y);
            //cout<<need.x<<" "<<need.y<<endl;
        }
    }
    vector<int>save;
    for(int i=1;i<=q;i++)
    {
        ans[i]=(ans[i]>0)?1:0;
        save.push_back(ans[i]);
    }
    return save;
 
}

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