oj.uz

Submission #519876

# Submission time Handle Problem Language Result Execution time Memory
519876 2022-01-27T13:39:41 Z oneloveforever Werewolf (IOI18_werewolf) C++14
15 / 100
 866 ms 518120 KB 
#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=1e5+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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24108 KB Output is correct
2 Correct 11 ms 23844 KB Output is correct
3 Correct 10 ms 23728 KB Output is correct
4 Correct 10 ms 23756 KB Output is correct
5 Correct 11 ms 23920 KB Output is correct
6 Correct 11 ms 23904 KB Output is correct
7 Correct 11 ms 23884 KB Output is correct
8 Correct 10 ms 23756 KB Output is correct
9 Correct 11 ms 24268 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24108 KB Output is correct
2 Correct 11 ms 23844 KB Output is correct
3 Correct 10 ms 23728 KB Output is correct
4 Correct 10 ms 23756 KB Output is correct
5 Correct 11 ms 23920 KB Output is correct
6 Correct 11 ms 23904 KB Output is correct
7 Correct 11 ms 23884 KB Output is correct
8 Correct 10 ms 23756 KB Output is correct
9 Correct 11 ms 24268 KB Output is correct
10 Correct 672 ms 142684 KB Output is correct
11 Correct 688 ms 108760 KB Output is correct
12 Correct 695 ms 28508 KB Output is correct
13 Correct 831 ms 518120 KB Output is correct
14 Correct 866 ms 518080 KB Output is correct
15 Correct 812 ms 121212 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 455 ms 352776 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24108 KB Output is correct
2 Correct 11 ms 23844 KB Output is correct
3 Correct 10 ms 23728 KB Output is correct
4 Correct 10 ms 23756 KB Output is correct
5 Correct 11 ms 23920 KB Output is correct
6 Correct 11 ms 23904 KB Output is correct
7 Correct 11 ms 23884 KB Output is correct
8 Correct 10 ms 23756 KB Output is correct
9 Correct 11 ms 24268 KB Output is correct
10 Correct 672 ms 142684 KB Output is correct
11 Correct 688 ms 108760 KB Output is correct
12 Correct 695 ms 28508 KB Output is correct
13 Correct 831 ms 518120 KB Output is correct
14 Correct 866 ms 518080 KB Output is correct
15 Correct 812 ms 121212 KB Output is correct
16 Runtime error 455 ms 352776 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -