oj.uz

Submission #519878

# Submission time Handle Problem Language Result Execution time Memory
519878 2022-01-27T13:43:02 Z oneloveforever Werewolf (IOI18_werewolf) C++14
7 / 100
 4000 ms 524292 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=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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 70980 KB Output is correct
2 Correct 27 ms 70856 KB Output is correct
3 Correct 26 ms 70708 KB Output is correct
4 Correct 26 ms 70676 KB Output is correct
5 Correct 27 ms 70868 KB Output is correct
6 Correct 30 ms 70860 KB Output is correct
7 Correct 27 ms 70860 KB Output is correct
8 Correct 28 ms 70804 KB Output is correct
9 Correct 29 ms 71300 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 70980 KB Output is correct
2 Correct 27 ms 70856 KB Output is correct
3 Correct 26 ms 70708 KB Output is correct
4 Correct 26 ms 70676 KB Output is correct
5 Correct 27 ms 70868 KB Output is correct
6 Correct 30 ms 70860 KB Output is correct
7 Correct 27 ms 70860 KB Output is correct
8 Correct 28 ms 70804 KB Output is correct
9 Correct 29 ms 71300 KB Output is correct
10 Correct 702 ms 189624 KB Output is correct
11 Correct 668 ms 155636 KB Output is correct
12 Correct 658 ms 75380 KB Output is correct
13 Runtime error 651 ms 524292 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4083 ms 351772 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 70980 KB Output is correct
2 Correct 27 ms 70856 KB Output is correct
3 Correct 26 ms 70708 KB Output is correct
4 Correct 26 ms 70676 KB Output is correct
5 Correct 27 ms 70868 KB Output is correct
6 Correct 30 ms 70860 KB Output is correct
7 Correct 27 ms 70860 KB Output is correct
8 Correct 28 ms 70804 KB Output is correct
9 Correct 29 ms 71300 KB Output is correct
10 Correct 702 ms 189624 KB Output is correct
11 Correct 668 ms 155636 KB Output is correct
12 Correct 658 ms 75380 KB Output is correct
13 Runtime error 651 ms 524292 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -