Submission #1011032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011032		danikoynov	Virus Experiment (JOI19_virus)	C++14	100 / 100	268 ms	81928 KiB

virus

#include<bits/stdc++.h>
#define endl '\n'

typedef long long ll;

const int MAX_R = 810;

struct Cell
{
    int x, y;
    
    Cell(int _x = 0, int _y = 0)
    {
        x = _x;
        y = _y;
    }

    Cell operator + (const Cell &c) const
    {
        return Cell(x + c.x, y + c.y);
    }
};

Cell neib[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int m, r, c;
std::string d;

int u[MAX_R][MAX_R];
void input()
{
    std::cin >> m >> r >> c;
    std::cin >> d;
    for (int i = 1; i <= r; i ++)
        for (int j = 1; j <= c; j ++)
            std::cin >> u[i][j];
}

int get_index(int i, int j)
{
    return (i - 1) * c + j;
}


std::string dir = "NESW";

int comp[MAX_R][MAX_R];
int par[MAX_R * MAX_R];
std::vector < Cell > dsu_comp[MAX_R * MAX_R];
int used[MAX_R][MAX_R];
int lon[(1 << 4) + 1];
int is_dead[MAX_R * MAX_R];
void find_longest(int mask)
{
    int cnt = 0;
    for (int i = 0; i < m; i ++)
    {
        for (int j = 0; j < 4; j ++)
        {
            if (d[i] != dir[j])
                continue;

            if ((mask & (1 << j)) > 0)
                cnt ++;
            else
            {
                lon[mask] = std::max(lon[mask], cnt);
                cnt = 0;
            }
            
        }
    }
    if (cnt == m)
        cnt = 2e9 + 10;
    ///std::cout << cnt << endl;
    lon[mask] = std::max(lon[mask], cnt);
    cnt = 0;
}

void init()
{
    for (int i = 1; i <= r; i ++)
        for (int j = 1; j <= c; j ++)
        {
            if (u[i][j] == 0)
                continue;
            par[get_index(i, j)] = get_index(i, j);
            comp[i][j] = get_index(i, j);
            dsu_comp[get_index(i, j)].push_back(Cell(i, j));
        }

    d = d + d;
    m = 2 * m;
    for (int mask = 0; mask < (1 << 4); mask ++)
        find_longest(mask);
}   

int find_leader(int v)
{
    if (v == par[v])
        return v;
    return (par[v] = find_leader(par[v]));
}

std::pair < int, int > bfs(int s)
{
    //std::cout << "start bfs " << endl;
    for (Cell cur : dsu_comp[s])
    {
        used[cur.x][cur.y] = 0;
    }
    /**std::cout << "USED" << endl;
    for (int i = 1; i <= r; i ++, std::cout << endl)
        for (int j = 1; j <= c; j ++)
            std::cout << used[i][j] << " ";*/
    std::queue < Cell > q;
    q.push(dsu_comp[s].back());
    used[q.front().x][q.front().y] = 1;

    int cnt = 0;
    while(!q.empty())
    {
        Cell cur = q.front();
        q.pop();
        ///std::cout << "cell " << cur.x << " " << cur.y << endl;
        cnt ++;
        for (int i = 0; i < 4; i ++)
        {
            Cell nb = cur + neib[i];
            if (nb.x < 1 || nb.x > r || nb.y < 1 || nb.y > c || u[nb.x][nb.y] == 0)
                continue;
            
            int mask = 0;
            for (int j = 0; j < 4; j ++)
            {
                Cell ds = nb + neib[j];
                if (ds.x < 1 || ds.x > r || ds.y < 1 || ds.y > c)
                    continue;
                if (used[ds.x][ds.y] == 1 && find_leader(comp[ds.x][ds.y]) == s)
                    mask |= (1 << j);
            }
            ///std::cout << "neib: " << nb.x << " " << nb.y << " " << mask << " " << lon[mask] << endl; 
        
            if (lon[mask] >= u[nb.x][nb.y])
            {
                if (find_leader(get_index(nb.x, nb.y)) == s)
                {
                    if (!used[nb.x][nb.y])  
                    {   
                        used[nb.x][nb.y] = 1;
                        q.push(nb);
                    }
                }
                else
                {
                    //std::cout << "fuck here" << endl;
                    return {1, comp[nb.x][nb.y]};
                }
            }
        }
    }

    return {-1, cnt};
}

int marked[MAX_R * MAX_R];

void unite(int v, int u)
{
    v = find_leader(v);
    u = find_leader(u);
    if (v == u)
        return;
    if (is_dead[u])
        is_dead[v] = 1;
    
    if (dsu_comp[v].size() > dsu_comp[u].size())
    {
        for (Cell cur : dsu_comp[u])
        {
            dsu_comp[v].push_back(cur);
            comp[cur.x][cur.y] = v;
        }
        par[u] = v;
    }
    else
    {
        Cell spec = dsu_comp[u].back();
        dsu_comp[u].pop_back();
        for (Cell cur : dsu_comp[v])
        {
            dsu_comp[u].push_back(cur);
            comp[cur.x][cur.y] = u;
        }
        par[v] = u;
        dsu_comp[u].push_back(spec);
    }
}

void union_process()
{
    std::pair < int, int > res = {1e9, 0};

    int cycle =0 ;
    while(true)
    {
        cycle ++;
        ///assert(cycle < 20);
        //if (cycle == 3)
          //  break;
        std::vector < std :: pair < int, int > > edges;
        for (int i = 1; i <= r * c; i ++)
            marked[i] = 0;
        
        bool done = true;
        for (int i = 1; i <= r * c; i ++)
        {
            
            int lead = find_leader(i);
            if (lead == 0)
                continue;
            
            if (marked[lead] || is_dead[lead])
                continue;
            marked[lead] = 1;
            done = false;
            //std::cout << "start from " << i << endl;
            std::pair < int, int > cur = bfs(lead);

            if (cur.first == -1)
            {
                if (cur.second < res.first)  res = {cur.second, 0};
                if (cur.second == res.first) res.second += cur.second;
                is_dead[lead] = 1;
            }
            else
            {
                edges.push_back({i, cur.second});
            }
            ///std::cout << "out " << endl;
        }


        if (done)
            break;
        for (std::pair < int, int > road : edges)
        {
            unite(road.first, road.second);
        }

    }


    std::cout << res.first << endl << res.second << endl;
}
void solve()
{
    input();
    init();
    union_process();
}

void speed()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}
int main()
{
    ///freopen("test.txt", "r", stdin);
    speed();
    solve();
    return 0;
}
/**

*/

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