Submission #1245006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245006		Zbyszek99	Virus Experiment (JOI19_virus)	C++20	100 / 100	503 ms	231980 KiB

virus

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<long long>
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
//mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

vector<pii> dirs = {{-1,0},{0,1},{1,0},{0,-1}};
map<char,int> dir_map = {{'N',0},{'E',1},{'S',2},{'W',3}};
int dir[100002];
int pref[100002][4];
int mask_len[16];
int arr[802][802];
vi my_masks[802][802];
vector<pii> mask_dirs[16];

int rep_[802][802];
vector<pii> comp_list[802*802];
vector<pii> edges_ok[802*802];
vector<pii> edges_not_ok[802*802];
bool can_ans[802*802];
bool odw[8002*802];

int get_edge(int a)
{
    while(siz(edges_ok[a]) > 0)
    {
        pii p = edges_ok[a].back();
        if(rep_[p.ff][p.ss] == a)
        {
            edges_ok[a].pop_back();
            continue;
        }
        return rep_[p.ff][p.ss];
    }
    return -1;
}

bool can_con(int x1, int y1, int c)
{
    forall(it,my_masks[x1][y1])
    {
        int cnt = 0;
        forall(d,mask_dirs[it])
        {
            if(rep_[x1+d.ff][y1+d.ss] == c) cnt++;
        }
        if(cnt == siz(mask_dirs[it])) return 1;
    }
    return 0;
}

int onion(int a, int b)
{
    if(a == b) return a;
    if(siz(edges_ok[a]) + siz(edges_not_ok[a]) > siz(edges_ok[b]) + siz(edges_not_ok[b])) swap(a,b);
    forall(it,comp_list[a])
    {
        rep_[it.ff][it.ss] = b;
        comp_list[b].pb(it);
    }
    forall(it,edges_ok[a]) edges_ok[b].pb(it);
    forall(it,edges_not_ok[a])
    {
        if(can_con(it.ff,it.ss,b)) edges_ok[b].pb(it);
        else edges_not_ok[b].pb(it);
    }
    return b;
}


int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random();
    int m,r,c;
    cin >> m >> c >> r;
    int cnt = 0;
    rep2(i,0,801) rep2(j,0,801) {comp_list[cnt] = {{i,j}}; rep_[i][j] = cnt++;} 
    string s;
    cin >> s;
    rep2(i,1,m) dir[i] = dir_map[s[i-1]];
    rep2(i,1,m)
    {
        rep(d,4) pref[i][d] = pref[i-1][d];
        pref[i][dir[i]]++;
    }
    rep2(mask,1,15)
    {
        vi used;
        rep(i,4)
        {
            if((1 << i) & mask) 
            {
                mask_dirs[mask].pb(dirs[i]);
                used.pb(i);
            }
        }
        rep2(i,1,m)
        {
            int len = 0;
            forall(it,used) len += pref[m][it] - pref[i-1][it];
            if(len == m-i+1)
            {
                int l = 1;
                int r = i-1;
                int ans = 0;
                while(l <= r)
                {
                    int mid = (l+r)/2;
                    int len2 = 0;
                    forall(it,used) len2 += pref[mid][it];
                    if(len2 == mid)
                    {
                        ans = mid;
                        l = mid+1;
                    }
                    else
                    {
                        r = mid-1;
                    }
                }
                mask_len[mask] = max(mask_len[mask],len+ans);
            }
            else
            {
                int l = i;
                int r = m;
                int ans = i-1;
                while(l <= r)
                {
                    int mid = (l+r)/2;
                    int len2 = 0;
                    forall(it,used) len2 += pref[mid][it] - pref[i-1][it];
                    if(len2 == mid-i+1)
                    {
                        ans = mid;
                        l = mid+1;
                    }
                    else
                    {
                        r = mid-1;
                    }
                }
                mask_len[mask] = max(mask_len[mask],ans-i+1);
            }
        }
    }
    rep2(i,1,c)
    {
        rep2(j,1,r)
        {
            cin >> arr[i][j];
        }
    }
    rep2(i,1,c)
    {
        rep2(j,1,r)
        {
            if(arr[i][j] == 0) continue;
            rep2(mask,1,15)
            {
                if(mask_len[mask] >= min(arr[i][j],m)) my_masks[i][j].pb(mask);
            }
        }
    }
    rep2(i,1,c)
    {
        rep2(j,1,r)
        {
            forall(d,dirs)
            {
                if(can_con(i+d.ff,j+d.ss,rep_[i][j])) edges_ok[rep_[i][j]].pb({i+d.ff,j+d.ss});
                else edges_not_ok[rep_[i][j]].pb({i+d.ff,j+d.ss});
            }
        }
    }
    rep2(i,1,c)
    {
        rep2(j,1,r)
        {
            if(odw[rep_[i][j]] == 0 && arr[i][j] > 0)
            {
                int cur = rep_[i][j];
                vi st;
                while(true)
                {
                    st.pb(cur);
                    odw[cur] = 1;
                    int nxt = get_edge(cur);
                    if(nxt == -1)
                    {
                        can_ans[cur] = 1;
                        break;
                    }
                    if(odw[nxt] == 1)
                    {
                        vi con;
                        bool is = 0;
                        while(!st.empty())
                        {
                            con.pb(st.back());
                            if(st.back() == nxt)
                            {
                                st.pop_back();
                                is = 1;
                                break;
                            }
                            st.pop_back();
                        }
                        if(is == 0) break;
                        forall(it,con)
                        {
                            cur = onion(cur,it);
                        }
                    }
                    else cur = nxt;
                }
            }
        }
    }
    int min_ = 1e9;
    cnt = 0;
    rep(i,802*802) 
    {
        if(can_ans[i])
        {
            if(min_ == siz(comp_list[i]))
            {
                cnt += siz(comp_list[i]);
            }
            else if(min_ > siz(comp_list[i]))
            {
                cnt = siz(comp_list[i]);
                min_ = siz(comp_list[i]);
            }
        }
    }
    cout << min_ << "\n" << cnt;
}

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