Submission #1169354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169354		duccnamm	늑대인간 (IOI18_werewolf)	C++20	100 / 100	536 ms	90848 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define ll int
ll n,m,q,f[200005],in1[200005],out1[200005],timedfs1,pos1[200005],in2[200005],out2[200005],timedfs2,st[200005][19][2],d1,d2,query1[200005],query2[200005],u,v,seg[800005];
vector<ll>a[200005],aa[200005];
struct node
{
    ll a,b,c,d;
};
vector<node>query[200005];
vector<ll>ans;
ll check(ll i)
{
    if(f[i]<0)
        return i;
    return f[i]=check(f[i]);
}
void connect(ll x,ll y,ll z)
{
    if(x>y&&z==1)
        swap(x,y);
    if(x<y&&z==2)
        swap(x,y);
    f[x]+=f[y];
    f[y]=x;
}
void dfs(ll x,ll pa)
{
    st[x][0][0]=pa;
    timedfs1++;
    in1[x]=timedfs1;
    pos1[timedfs1]=x;
    for(ll it:aa[x])
        if(it!=pa)
            dfs(it,x);
    out1[x]=timedfs1;
}
void dfs1(ll x,ll pa)
{
//    cout<<x<<" "<<pa<<'\n';
    st[x][0][1]=pa;
    timedfs2++;
    in2[x]=timedfs2;
    for(ll it:aa[x])
        if(it!=pa)
            dfs1(it,x);
    out2[x]=timedfs2;
}
void update(ll id,ll l,ll r,ll u,ll v)
{
    if(l>u||r<u)return;
    if(l==r)
    {
        seg[id]=v;
        return;
    }
    ll mid=(l+r)/2;
    update(id*2,l,mid,u,v);
    update(id*2+1,mid+1,r,u,v);
    seg[id]=max(seg[id*2],seg[id*2+1]);
}
ll getmax(ll id,ll l,ll r,ll u,ll v)
{
    if(r<u||l>v)
        return 0;
    if(l>=u&&r<=v)
        return seg[id];
    ll mid=(l+r)/2;
    return max(getmax(id*2,l,mid,u,v),getmax(id*2+1,mid+1,r,u,v));
}
vector<ll> check_validity(int N,vector<ll>X,vector<ll>Y,vector<ll>S,vector<ll>E,vector<ll>L,vector<ll>R)
{
    n=N;
    m=X.size();
    q=S.size();
    for(int i=0;i<m;i++)
    {
        a[X[i]+1].push_back(Y[i]+1);
        a[Y[i]+1].push_back(X[i]+1);
    }
    for(int i=1;i<=n;i++)
        f[i]=-1;
    for(int i=n;i>=1;i--)
        for(ll it:a[i])
            if(it>i)
            {
                u=check(it);
                v=check(i);
                if(u!=v)
                {
                    aa[v].push_back(u);
                    aa[u].push_back(v);
//                    cout<<u<<" "<<v<<'\n';
                    connect(u,v,1);
                }
            }
    dfs(1,1);
    for(int j=1;j<=18;j++)
        for(int i=1;i<=n;i++)
            st[i][j][0]=st[st[i][j-1][0]][j-1][0];
    for(int i=0;i<q;i++)
    {
        d1=L[i]+1;
        d2=S[i]+1;
        for(int j=18;j>=0;j--)
            if(st[d2][j][0]>=d1)
                d2=st[d2][j][0];
        query1[i+1]=d2;
    }
    for(int i=1;i<=n;i++)
    {
        f[i]=-1;
        aa[i].clear();
    }
    for(int i=1;i<=n;i++)
        for(ll it:a[i])
            if(it<i)
            {
                u=check(it);
                v=check(i);
                if(u!=v)
                {
                    aa[v].push_back(u);
                    aa[u].push_back(v);
//                    cout<<u<<" "<<v<<'\n';
                    connect(u,v,2);
                }
            }
    dfs1(n,n);
    for(int j=1;j<=18;j++)
        for(int i=1;i<=n;i++)
            st[i][j][1]=st[st[i][j-1][1]][j-1][1];
    for(int i=0;i<q;i++)
    {
        d1=R[i]+1;
        d2=E[i]+1;
        for(int j=18;j>=0;j--)
            if(st[d2][j][1]<=d1)
                d2=st[d2][j][1];
        query2[i+1]=d2;
//        cout<<query1[i+1]<<" "<<query2[i+1]<<'\n';
    }
//    for(int i=1;i<=n;i++)
//    {
//        cout<<i<<" "<<in1[i]<<" "<<out1[i]<<'\n';
//        cout<<i<<" "<<in2[i]<<" "<<out2[i]<<'\n';
//    }
    ans.resize(q);
    for(int i=1;i<=q;i++)
    {
//        cout<<query1[i]<<" "<<query2[i]<<" "<<in2[query1[i]]<<" "<<out2[query1[i]]<<'\n';
        query[out1[query1[i]]].push_back({in1[query1[i]],in2[query2[i]],out2[query2[i]],i-1});
    }
    for(int i=1;i<=n;i++)
    {
//        cout<<pos1[i]<<" "<<in2[pos1[i]]<<'\n';
        update(1,1,n,in2[pos1[i]],i);
        for(node it:query[i])
        {
//            cout<<i<<" "<<it.a<<" "<<it.b<<" "<<it.c<<" "<<it.d<<'\n';
            d1=getmax(1,1,n,it.b,it.c);
            if(d1>=it.a)
                ans[it.d]=1;
        }
    }
//    for(ll it:ans)
//        cout<<it<<" ";
    return ans;
}
//int main()
//{
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);cout.tie(0);
//    freopen("nam.inp","r",stdin);
//    freopen("nam.out","w",stdout);
//    cin>>n>>m>>q;
//    vector<ll>x,y,s,e,l,r;
//    x.resize(m);
//    y.resize(m);
//    s.resize(q);
//    e.resize(q);
//    l.resize(q);
//    r.resize(q);
//    for(int i=0;i<m;i++)
//        cin>>x[i];
//    for(int i=0;i<m;i++)
//        cin>>y[i];
//    for(int i=0;i<q;i++)
//        cin>>s[i];
//    for(int i=0;i<q;i++)
//        cin>>e[i];
//    for(int i=0;i<q;i++)
//        cin>>l[i];
//    for(int i=0;i<q;i++)
//        cin>>r[i];
//    check_validity(n,x,y,s,e,l,r);
//}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51