oj.uz

Submission #519877

# Submission time Handle Problem Language Result Execution time Memory
519877 2022-01-27T13:40:43 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 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 20 ms 47556 KB Output is correct
2 Correct 19 ms 47412 KB Output is correct
3 Correct 19 ms 47308 KB Output is correct
4 Correct 22 ms 47252 KB Output is correct
5 Correct 20 ms 47392 KB Output is correct
6 Correct 20 ms 47436 KB Output is correct
7 Correct 20 ms 47404 KB Output is correct
8 Correct 21 ms 47308 KB Output is correct
9 Correct 19 ms 47820 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47556 KB Output is correct
2 Correct 19 ms 47412 KB Output is correct
3 Correct 19 ms 47308 KB Output is correct
4 Correct 22 ms 47252 KB Output is correct
5 Correct 20 ms 47392 KB Output is correct
6 Correct 20 ms 47436 KB Output is correct
7 Correct 20 ms 47404 KB Output is correct
8 Correct 21 ms 47308 KB Output is correct
9 Correct 19 ms 47820 KB Output is correct
10 Correct 683 ms 166112 KB Output is correct
11 Correct 677 ms 132076 KB Output is correct
12 Correct 647 ms 51848 KB Output is correct
13 Runtime error 677 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 4059 ms 328276 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47556 KB Output is correct
2 Correct 19 ms 47412 KB Output is correct
3 Correct 19 ms 47308 KB Output is correct
4 Correct 22 ms 47252 KB Output is correct
5 Correct 20 ms 47392 KB Output is correct
6 Correct 20 ms 47436 KB Output is correct
7 Correct 20 ms 47404 KB Output is correct
8 Correct 21 ms 47308 KB Output is correct
9 Correct 19 ms 47820 KB Output is correct
10 Correct 683 ms 166112 KB Output is correct
11 Correct 677 ms 132076 KB Output is correct
12 Correct 647 ms 51848 KB Output is correct
13 Runtime error 677 ms 524292 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -