oj.uz

Submission #718792

# Submission time Handle Problem Language Result Execution time Memory
718792 2023-04-04T20:25:48 Z ogibogi2004 Werewolf (IOI18_werewolf) C++14
100 / 100
 1951 ms 390300 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e5+6;
const int logN=19;
struct node
{
    int left_child,right_child,maxval;
};
vector<node>nodes;
vector<int>g[MAXN];
int in_time[MAXN][2];
int out_time[MAXN][2];
int par[2][MAXN][logN];
int x[MAXN],y[MAXN];
int maxval[2][MAXN];
int what[MAXN];
struct tree_2d
{
    set<int>s[3*MAXN];
    void build(int l,int r,int idx)
    {
        for(int i=l;i<=r;i++)s[idx].insert(y[i]);
        if(l==r)return;
        int mid=(l+r)/2;

        build(l,mid,idx*2);
        build(mid+1,r,idx*2+1);
    }
    bool query(int l,int r,int idx,int ql,int qr,int ql1,int qr1)
    {
        if(l>qr)return 0;
        if(r<ql)return 0;
        if(l>=ql&&r<=qr)
        {
            auto it=s[idx].lower_bound(ql1);
            if(it!=s[idx].end()&&(*it)<=qr1)return 1;
            return 0;
        }
        int mid=(l+r)/2;
        return query(l,mid,idx*2,ql,qr,ql1,qr1)||query(mid+1,r,idx*2+1,ql,qr,ql1,qr1);
    }
}tr;
struct dsu
{
    int par[MAXN];
    void init()
    {
        for(int i=0;i<MAXN;i++)
        {
            par[i]=i;
        }
    }
    int getRoot(int u)
    {
        if(u==par[u])return u;
        return par[u]=getRoot(par[u]);
    }
    void join(int p,int q,int f)
    {
        p=getRoot(p);
        q=getRoot(q);
        if(p==q)return;
        //cout<<"merge "<<p<<" "<<q<<endl;
        int t=nodes.size();
        par[p]=t;par[q]=t;
        if(f)nodes.push_back({p,q,max(nodes[p].maxval,nodes[q].maxval)});
        else nodes.push_back({p,q,min(nodes[p].maxval,nodes[q].maxval)});
        //cout<<"new node "<<p<<" "<<q<<" "<<nodes.back().maxval<<endl;
    }
}dsu1;
int t,n;
void dfs(int u,int p,int f)
{
    in_time[u][f]=++t;
    par[f][u][0]=p;
    /*if(p!=0)
    {
        cout<<"in graph with f="<<f<<" "<<nodes[p].maxval<<" -> "<<nodes[u].maxval<<endl;
    }*/
    if(nodes[u].left_child!=-1)dfs(nodes[u].left_child,u,f);
    if(nodes[u].right_child!=-1)dfs(nodes[u].right_child,u,f);
    out_time[u][f]=t;
}
void precompute()
{
    for(int f=0;f<=1;f++)
    for(int step=1;step<logN;step++)
    {
        for(int i=0;i<nodes.size();i++)
        {
            if(par[f][i][step-1]==-1)par[f][i][step]=-1;
            else par[f][i][step]=par[f][par[f][i][step-1]][step-1];
        }
    }
}
int lift_left(int vert,int l)
{
    if(vert<l)return -1;
    for(int j=logN-1;j>=0;j--)
    {
        if(par[0][vert][j]==-1)continue;
        if(maxval[0][par[0][vert][j]]<l)continue;
        vert=par[0][vert][j];
    }
    return vert;
}
int lift_right(int vert,int r)
{
    if(vert>r)return -1;
    //cout<<vert<<" :\n";
    for(int j=logN-1;j>=0;j--)
    {
        if(par[1][vert][j]==-1)continue;
        if(maxval[1][par[1][vert][j]]>r)continue;
        vert=par[1][vert][j];
        //cout<<" -> "<<vert<<" "<<nodes[vert].maxval<<endl;
    }
    return vert;
}
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=0;i<X.size();i++)
        {
            g[X[i]].push_back(Y[i]);
            g[Y[i]].push_back(X[i]);
        }
        for(int i=0;i<N;i++)
        {
            nodes.push_back({-1,-1,i});
        }
        //cout<<"*0\n";
        dsu1.init();
        for(int i=N-1;i>=0;i--)
        {
            //cout<<"%% "<<i<<endl;
            for(auto xd:g[i])
            {
                if(xd>i)
                {
                    dsu1.join(xd,i,0);
                }
            }
        }
        t=0;
        //cout<<"*0.5\n";
        dfs(nodes.size()-1,-1,0);
        for(int i=0;i<nodes.size();i++)maxval[0][i]=nodes[i].maxval;
        //cout<<"*1\n";
        nodes.clear();
        for(int i=0;i<N;i++)
        {
            nodes.push_back({-1,-1,i});
        }
        dsu1.init();
        for(int i=0;i<N;i++)
        {
            for(auto xd:g[i])
            {
                if(xd<i)
                {
                    dsu1.join(xd,i,1);
                }
            }
        }
        t=0;
        dfs(nodes.size()-1,-1,1);

        precompute();

        //cout<<"*2\n";
        for(int i=0;i<N;i++)
        {
            x[i]=in_time[i][0];
            y[x[i]]=in_time[i][1];
            //what[x[i]]=i;
            //cout<<i<<": "<<x[i]<<" "<<y[x[i]]<<endl;
        }
        tr.build(1,nodes.size(),1);
        for(int i=0;i<nodes.size();i++)maxval[1][i]=nodes[i].maxval;
        vector<int>ans;
        //cout<<"*3\n";
        for(int i=0;i<L.size();i++)
        {
            int t1=lift_left(S[i],L[i]);
            int t2=lift_right(E[i],R[i]);
            /*if(t1==-1||t2==-1)cout<<"-1\n";
            else
            {
                cout<<in_time[t1][0]<<" "<<out_time[t1][0]<<" "<<in_time[t2][1]<<" "<<out_time[t2][1]<<endl;
                cout<<nodes[t1].maxval<<" "<<nodes[t2].maxval<<endl;
                cout<<t1<<" "<<t2<<endl;
            }*/
            if(t1!=-1&&t2!=-1&&tr.query(1,nodes.size(),1,in_time[t1][0], out_time[t1][0],in_time[t2][1],out_time[t2][1]))
            {
                ans.push_back(1);
            }
            else
            {
                ans.push_back(0);
            }
            //cout<<ans.back()<<endl;
        }
        return ans;
}

Compilation message

werewolf.cpp: In function 'void precompute()':
werewolf.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for(int i=0;i<nodes.size();i++)
      |                     ~^~~~~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:126:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         for(int i=0;i<X.size();i++)
      |                     ~^~~~~~~~~
werewolf.cpp:151:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |         for(int i=0;i<nodes.size();i++)maxval[0][i]=nodes[i].maxval;
      |                     ~^~~~~~~~~~~~~
werewolf.cpp:183:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |         for(int i=0;i<nodes.size();i++)maxval[1][i]=nodes[i].maxval;
      |                     ~^~~~~~~~~~~~~
werewolf.cpp:186:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |         for(int i=0;i<L.size();i++)
      |                     ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 67788 KB Output is correct
2 Correct 33 ms 67684 KB Output is correct
3 Correct 32 ms 67660 KB Output is correct
4 Correct 36 ms 67588 KB Output is correct
5 Correct 33 ms 67708 KB Output is correct
6 Correct 32 ms 67752 KB Output is correct
7 Correct 37 ms 67664 KB Output is correct
8 Correct 36 ms 67660 KB Output is correct
9 Correct 34 ms 67728 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 67788 KB Output is correct
2 Correct 33 ms 67684 KB Output is correct
3 Correct 32 ms 67660 KB Output is correct
4 Correct 36 ms 67588 KB Output is correct
5 Correct 33 ms 67708 KB Output is correct
6 Correct 32 ms 67752 KB Output is correct
7 Correct 37 ms 67664 KB Output is correct
8 Correct 36 ms 67660 KB Output is correct
9 Correct 34 ms 67728 KB Output is correct
10 Correct 43 ms 71500 KB Output is correct
11 Correct 43 ms 71508 KB Output is correct
12 Correct 48 ms 71444 KB Output is correct
13 Correct 47 ms 71628 KB Output is correct
14 Correct 46 ms 71656 KB Output is correct
15 Correct 48 ms 71704 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1485 ms 370688 KB Output is correct
2 Correct 1594 ms 383768 KB Output is correct
3 Correct 1385 ms 380764 KB Output is correct
4 Correct 1304 ms 379376 KB Output is correct
5 Correct 1394 ms 379316 KB Output is correct
6 Correct 1445 ms 379376 KB Output is correct
7 Correct 1350 ms 379096 KB Output is correct
8 Correct 1457 ms 383864 KB Output is correct
9 Correct 1243 ms 380736 KB Output is correct
10 Correct 1226 ms 379388 KB Output is correct
11 Correct 1274 ms 379308 KB Output is correct
12 Correct 1140 ms 379216 KB Output is correct
13 Correct 1855 ms 377204 KB Output is correct
14 Correct 1838 ms 377156 KB Output is correct
15 Correct 1916 ms 377244 KB Output is correct
16 Correct 1844 ms 377180 KB Output is correct
17 Correct 1429 ms 379060 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 67788 KB Output is correct
2 Correct 33 ms 67684 KB Output is correct
3 Correct 32 ms 67660 KB Output is correct
4 Correct 36 ms 67588 KB Output is correct
5 Correct 33 ms 67708 KB Output is correct
6 Correct 32 ms 67752 KB Output is correct
7 Correct 37 ms 67664 KB Output is correct
8 Correct 36 ms 67660 KB Output is correct
9 Correct 34 ms 67728 KB Output is correct
10 Correct 43 ms 71500 KB Output is correct
11 Correct 43 ms 71508 KB Output is correct
12 Correct 48 ms 71444 KB Output is correct
13 Correct 47 ms 71628 KB Output is correct
14 Correct 46 ms 71656 KB Output is correct
15 Correct 48 ms 71704 KB Output is correct
16 Correct 1485 ms 370688 KB Output is correct
17 Correct 1594 ms 383768 KB Output is correct
18 Correct 1385 ms 380764 KB Output is correct
19 Correct 1304 ms 379376 KB Output is correct
20 Correct 1394 ms 379316 KB Output is correct
21 Correct 1445 ms 379376 KB Output is correct
22 Correct 1350 ms 379096 KB Output is correct
23 Correct 1457 ms 383864 KB Output is correct
24 Correct 1243 ms 380736 KB Output is correct
25 Correct 1226 ms 379388 KB Output is correct
26 Correct 1274 ms 379308 KB Output is correct
27 Correct 1140 ms 379216 KB Output is correct
28 Correct 1855 ms 377204 KB Output is correct
29 Correct 1838 ms 377156 KB Output is correct
30 Correct 1916 ms 377244 KB Output is correct
31 Correct 1844 ms 377180 KB Output is correct
32 Correct 1429 ms 379060 KB Output is correct
33 Correct 1886 ms 380788 KB Output is correct
34 Correct 318 ms 100220 KB Output is correct
35 Correct 1951 ms 383720 KB Output is correct
36 Correct 1718 ms 379852 KB Output is correct
37 Correct 1925 ms 383244 KB Output is correct
38 Correct 1767 ms 380604 KB Output is correct
39 Correct 1509 ms 390216 KB Output is correct
40 Correct 1816 ms 387536 KB Output is correct
41 Correct 1647 ms 382532 KB Output is correct
42 Correct 1495 ms 379776 KB Output is correct
43 Correct 1884 ms 386356 KB Output is correct
44 Correct 1945 ms 382908 KB Output is correct
45 Correct 1355 ms 390300 KB Output is correct
46 Correct 1462 ms 389932 KB Output is correct
47 Correct 1912 ms 377248 KB Output is correct
48 Correct 1865 ms 377128 KB Output is correct
49 Correct 1861 ms 377204 KB Output is correct
50 Correct 1888 ms 377200 KB Output is correct
51 Correct 1600 ms 388472 KB Output is correct
52 Correct 1590 ms 388380 KB Output is correct