oj.uz

Submission #519879

# Submission time Handle Problem Language Result Execution time Memory
519879 2022-01-27T13:52:27 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=2e5+7;
const int N=4e5+7;
const int LOG=20;
int n;
int trace[M][LOG+10][2],beg[M][2],fin[M][2],id[M][2],pre[2];
vector<int>a[M];
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;
    }
};
vector<node>query[N];
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 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;
    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();
    for(int i=1;i<=q;i++)
    {
        int x=S[i-1]+1;
        int y=E[i-1]+1;
        int u=L[i-1]+1;
        int v=R[i-1]+1;
        for(int node=LOG;node>=0;node--)
        {
            if(trace[x][node][0]==-1)continue;
            if(trace[x][node][0]>=u)x=trace[x][node][0];
        }
        for(int node=LOG;node>=0;node--)
        {
            if(trace[y][node][1]==-1)continue;
            if(trace[y][node][1]<=v)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);
    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-1]+=need.value*bit.get_sum(need.x,need.y);
            //cout<<need.x<<" "<<need.y<<endl;
        }
    }
    for(int i=0;i<=q-1;i++)
    {
        ans[i]=(ans[i]>0)?1:0;
    }
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 61700 KB Output is correct
2 Correct 28 ms 61384 KB Output is correct
3 Correct 33 ms 61404 KB Output is correct
4 Correct 28 ms 61388 KB Output is correct
5 Correct 30 ms 61548 KB Output is correct
6 Correct 26 ms 61516 KB Output is correct
7 Correct 26 ms 61480 KB Output is correct
8 Correct 26 ms 61380 KB Output is correct
9 Correct 27 ms 61928 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 61700 KB Output is correct
2 Correct 28 ms 61384 KB Output is correct
3 Correct 33 ms 61404 KB Output is correct
4 Correct 28 ms 61388 KB Output is correct
5 Correct 30 ms 61548 KB Output is correct
6 Correct 26 ms 61516 KB Output is correct
7 Correct 26 ms 61480 KB Output is correct
8 Correct 26 ms 61380 KB Output is correct
9 Correct 27 ms 61928 KB Output is correct
10 Correct 741 ms 180220 KB Output is correct
11 Correct 723 ms 146160 KB Output is correct
12 Correct 657 ms 65928 KB Output is correct
13 Runtime error 628 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 4073 ms 337792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 61700 KB Output is correct
2 Correct 28 ms 61384 KB Output is correct
3 Correct 33 ms 61404 KB Output is correct
4 Correct 28 ms 61388 KB Output is correct
5 Correct 30 ms 61548 KB Output is correct
6 Correct 26 ms 61516 KB Output is correct
7 Correct 26 ms 61480 KB Output is correct
8 Correct 26 ms 61380 KB Output is correct
9 Correct 27 ms 61928 KB Output is correct
10 Correct 741 ms 180220 KB Output is correct
11 Correct 723 ms 146160 KB Output is correct
12 Correct 657 ms 65928 KB Output is correct
13 Runtime error 628 ms 524292 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -