제출 #718792

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
718792		ogibogi2004	늑대인간 (IOI18_werewolf)	C++14	100 / 100	1951 ms	390300 KiB

werewolf

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51