제출 #441521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
441521		fcmalkcin	Virus Experiment (JOI19_virus)	C++17	100 / 100	1071 ms	262144 KiB

virus

#include <bits/stdc++.h>
using namespace std;
#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn=6e5+4e4+100;
const ll mod =998244353 ;
const ll base=3e18;
set<ll> adj[maxn];
set<ll> adv[maxn];
vector<pll> nxt[maxn];
ll ax[5]= {-1,0,1,0};
ll ay[5]= {0,1,0,-1};
ll a[maxn];
ll par[maxn];
ll n, m;
ll p;
ll dd[maxn];
ll msk[18];
bool chk[maxn];
ll hsh(ll i,ll j)
{
    return i*m+j;
}
ll find_par(ll u)
{
    if (par[u]<0)
        return u;
    return par[u]=find_par(par[u]);
}

void dsu(ll x,ll y)
{
    x=find_par(x);
    y=find_par(y);
    if (x==y)
        return ;
      //  cout <<x<<" "<<y<<endl;
    par[x]+=par[y];
    par[y]=x;
    if (adj[y].size()+adv[y].size()>adj[x].size()+adv[x].size())
    {
        swap(adj[x],adj[y]);
        swap(adv[x],adv[y]);
    }
    for (auto to:adv[y])
        adv[x].insert(to);
    for (auto u:adj[y])
    {
        ll nw=0;
        for (auto p:nxt[u])
        {
            ll u=p.ff;
            ll id=p.ss;
            if (find_par(u)==x)
            {
                nw+=(1ll<<id);
            }
        }
        if (msk[nw]>=a[u])
            adv[x].insert(u);
        else
            adj[x].insert(u);
    }
    adj[y].clear();
    adv[y].clear();
}
void popfront(ll x)
{
    while (!adv[x].empty())
    {
        ll v=*adv[x].begin();
        if (find_par(v)==x)
        {
            adv[x].erase(v);
        }
        else if (find_par(v)!=v)
        {
            adv[x].insert(find_par(v));
            adv[x].erase(v);
        }
        else
            break;
    }
}
void dosth(ll x)
{
    stack<ll> st;
    st.push(x);
    dd[x]=1;
    while (!st.empty())
    {
        auto u=st.top();
        popfront(u);
        if (adv[u].size()==0)
        {
            dd[u]=2;
            st.pop();
            continue;
        }
        ll v=*adv[u].begin();
        adv[u].erase(v);
       // cout <<u<<" "<<v<<endl;
        if (dd[v]==2)
            continue;
        if (dd[v]==1)
        {
            while (st.top()!=v)
                dsu(v,st.top()),dd[st.top()]=2,st.pop();
        }
        else
        {
            dd[v]=1;
            st.push(v);
        }

    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    memset(par,-1,sizeof(par));
    cin>>p>> n>> m;
    string s;
    cin>> s;
    for (int i=0; i<p; i++)
    {
        if (s[i]=='N')
            s[i]='0';
        else if (s[i]=='E')
            s[i]='1';
        else if (s[i]=='S')
            s[i]='2';
        else
            s[i]='3';
    }
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
            cin>>a[hsh(i,j)];
            if (!a[hsh(i,j)])
            {
                a[hsh(i,j)]=base+1;
                dd[hsh(i,j)]=2;
                chk[hsh(i,j)]=1;
            }

        }
    }
    p+=p;
    s+=s;
    for (int i=1; i<16; i++)
    {
        ll pre=-1;
        for (int j=0; j<p; j++)
        {
            ll t=s[j]-'0';
            // cout <<t<<endl;
            if (i&(1ll<<t))
                msk[i]=max(msk[i],j-pre);
            else
                pre=j;
        }
        if (msk[i]==p)
            msk[i]=base;
        //   cout<<msk[i]<<" ";
    }
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
            for (int t=0; t<4; t++)
            {

                ll x1=i+ax[t];
                ll y1=j+ay[t];
                if (x1>=0&&x1<n&&y1>=0&&y1<m)
                {
                    nxt[hsh(i,j)].pb(make_pair(hsh(x1,y1),t));
                    if (msk[(1ll<<t)]>=a[hsh(i,j)])
                    {
                        adv[hsh(x1,y1)].insert(hsh(i,j));
                    }
                    else
                    {
                        adj[hsh(x1,y1)].insert(hsh(i,j));
                    }
                }
            }
        }
    }
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
             if (!dd[hsh(i,j)]&&find_par(hsh(i,j))==hsh(i,j))
             {
             //   cout <<hsh(i,j)<<" "<<i<<" "<<j<<" chk"<<endl;
                 dosth(hsh(i,j));
             }
        }
    }

     for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
            ll u=hsh(i,j);
          //  cout <<u<<" "<<i<<" "<<j<<" "<<find_par(u)<<endl;
            for (auto p:nxt[u])
            {
               ll to=p.ff;
               if (find_par(to)==find_par(u)) continue;
               ll nw=0;
               for (auto p1:nxt[to])
               {
                  ll to1=p1.ff;
                  if (find_par(to1)==find_par(u)) nw+=(1ll<<(p1.ss));
               }
               if (msk[nw]>=a[to])
               {
                   chk[find_par(u)]=1;
               }
            }
        }
    }
    pll res=make_pair(base,0);
     for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
           ll u=hsh(i,j);
           if (!chk[find_par(u)])
           {
               ll siz=-par[find_par(u)];
               if (res.ff==siz) res.ss++;
               else if (res.ff>siz)
               {
                   res.ff=siz;
                   res.ss=1;
               }
           }
        }
    }
    cout <<res.ff<<endl;
    cout <<res.ss<<endl;


}

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

virus.cpp: In function 'int main()':
virus.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
virus.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 6 / 6
• Subtask 3: 80 / 80