oj.uz

Submission #519908

# Submission time Handle Problem Language Result Execution time Memory
519908 2022-01-27T14:34:36 Z oneloveforever Werewolf (IOI18_werewolf) C++14
100 / 100
 747 ms 141108 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],minv[M],maxv[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<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<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)
{
    n=N;
    for(int i=1;i<=n;i++)
    {
        for(int node=0;node<=LOG;node++)
        {
            for(int index=0;index<=1;index++)trace[i][node][index]=-1;
        }
    }
    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);
    }
    DSU s(n);
    for(int i=1;i<=n;i++)
    {
        for(int node:a[i])if(node<i)
        {
            s.conncet(i,node,1,maxv);
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int node:a[i])if(node>i)
        {
            s.conncet(i,node,0,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;
}
/*int main()
{
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    vector<int>x,y,s,e,l,r;
    for(int i=1; i<=m; i++)
    {
        int value_x,value_y;
        cin>>value_x>>value_y;
        x.push_back(value_x);
        y.push_back(value_y);
    }
    for(int i=1;i<=q;i++)
    {
        int value_s,value_e,value_l,value_r;
        cin>>value_s>>value_e>>value_l>>value_r;
        s.push_back(value_s);
        e.push_back(value_e);
        l.push_back(value_l);
        r.push_back(value_r);
    }
    vector<int> ans=check_validity(n,x,y,s,r,l,r);
    for(int node:ans)cout<<node<<endl;
}*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23820 KB Output is correct
2 Correct 12 ms 23884 KB Output is correct
3 Correct 14 ms 23816 KB Output is correct
4 Correct 12 ms 23780 KB Output is correct
5 Correct 12 ms 23756 KB Output is correct
6 Correct 11 ms 23776 KB Output is correct
7 Correct 11 ms 23760 KB Output is correct
8 Correct 12 ms 23788 KB Output is correct
9 Correct 12 ms 23756 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23820 KB Output is correct
2 Correct 12 ms 23884 KB Output is correct
3 Correct 14 ms 23816 KB Output is correct
4 Correct 12 ms 23780 KB Output is correct
5 Correct 12 ms 23756 KB Output is correct
6 Correct 11 ms 23776 KB Output is correct
7 Correct 11 ms 23760 KB Output is correct
8 Correct 12 ms 23788 KB Output is correct
9 Correct 12 ms 23756 KB Output is correct
10 Correct 17 ms 25292 KB Output is correct
11 Correct 17 ms 25196 KB Output is correct
12 Correct 17 ms 25164 KB Output is correct
13 Correct 18 ms 25444 KB Output is correct
14 Correct 17 ms 25548 KB Output is correct
15 Correct 18 ms 25384 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 113012 KB Output is correct
2 Correct 652 ms 127276 KB Output is correct
3 Correct 567 ms 122036 KB Output is correct
4 Correct 506 ms 119348 KB Output is correct
5 Correct 513 ms 119784 KB Output is correct
6 Correct 564 ms 120628 KB Output is correct
7 Correct 525 ms 119220 KB Output is correct
8 Correct 588 ms 127256 KB Output is correct
9 Correct 460 ms 120920 KB Output is correct
10 Correct 429 ms 119460 KB Output is correct
11 Correct 402 ms 119340 KB Output is correct
12 Correct 413 ms 119332 KB Output is correct
13 Correct 685 ms 132688 KB Output is correct
14 Correct 686 ms 132696 KB Output is correct
15 Correct 705 ms 132940 KB Output is correct
16 Correct 696 ms 132888 KB Output is correct
17 Correct 558 ms 118952 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23820 KB Output is correct
2 Correct 12 ms 23884 KB Output is correct
3 Correct 14 ms 23816 KB Output is correct
4 Correct 12 ms 23780 KB Output is correct
5 Correct 12 ms 23756 KB Output is correct
6 Correct 11 ms 23776 KB Output is correct
7 Correct 11 ms 23760 KB Output is correct
8 Correct 12 ms 23788 KB Output is correct
9 Correct 12 ms 23756 KB Output is correct
10 Correct 17 ms 25292 KB Output is correct
11 Correct 17 ms 25196 KB Output is correct
12 Correct 17 ms 25164 KB Output is correct
13 Correct 18 ms 25444 KB Output is correct
14 Correct 17 ms 25548 KB Output is correct
15 Correct 18 ms 25384 KB Output is correct
16 Correct 556 ms 113012 KB Output is correct
17 Correct 652 ms 127276 KB Output is correct
18 Correct 567 ms 122036 KB Output is correct
19 Correct 506 ms 119348 KB Output is correct
20 Correct 513 ms 119784 KB Output is correct
21 Correct 564 ms 120628 KB Output is correct
22 Correct 525 ms 119220 KB Output is correct
23 Correct 588 ms 127256 KB Output is correct
24 Correct 460 ms 120920 KB Output is correct
25 Correct 429 ms 119460 KB Output is correct
26 Correct 402 ms 119340 KB Output is correct
27 Correct 413 ms 119332 KB Output is correct
28 Correct 685 ms 132688 KB Output is correct
29 Correct 686 ms 132696 KB Output is correct
30 Correct 705 ms 132940 KB Output is correct
31 Correct 696 ms 132888 KB Output is correct
32 Correct 558 ms 118952 KB Output is correct
33 Correct 679 ms 121896 KB Output is correct
34 Correct 270 ms 62916 KB Output is correct
35 Correct 709 ms 126772 KB Output is correct
36 Correct 615 ms 121992 KB Output is correct
37 Correct 712 ms 125304 KB Output is correct
38 Correct 660 ms 122948 KB Output is correct
39 Correct 677 ms 141108 KB Output is correct
40 Correct 738 ms 131764 KB Output is correct
41 Correct 562 ms 123192 KB Output is correct
42 Correct 455 ms 119664 KB Output is correct
43 Correct 747 ms 133192 KB Output is correct
44 Correct 618 ms 125268 KB Output is correct
45 Correct 557 ms 140544 KB Output is correct
46 Correct 568 ms 140112 KB Output is correct
47 Correct 722 ms 132912 KB Output is correct
48 Correct 716 ms 132756 KB Output is correct
49 Correct 705 ms 132928 KB Output is correct
50 Correct 727 ms 132712 KB Output is correct
51 Correct 667 ms 132040 KB Output is correct
52 Correct 654 ms 132012 KB Output is correct