oj.uz

Submission #1011028

# Submission time Handle Problem Language Result Execution time Memory
1011028 2024-06-29T17:13:13 Z danikoynov Virus Experiment (JOI19_virus) C++14
20 / 100
 2000 ms 67880 KB 
#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 ++;
        //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;
            
            done = false;
            //std::cout << "start from " << i << endl;
            std::pair < int, int > cur = bfs(lead);
            //std::cout << "survive bfs " << cur.first << " " << cur.second << endl;
            if (cur.first == -1)
            {
                //std::cout << "kill" << endl;
                ///std::cout << "kill " << cur.second << endl;
                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;
        }

        ///std::cout << "fine after cycle " << endl;
        if (done)
            break;
        for (std::pair < int, int > road : edges)
        {
            //std::cout << "edge " << road.first << " " << road.second << endl;
            unite(road.first, road.second);
        }
        /**for (int i = 1; i <= r; i ++, std::cout << endl)
            for (int j = 1; j <= c; j ++)
            std::cout << find_leader(comp[i][j]) << " ";*/
        //exit(0);
    }


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

int main()
{
    ///freopen("test.txt", "r", stdin);
    solve();
    return 0;
}
/**

*/

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16220 KB Output is correct
2 Correct 176 ms 61392 KB Output is correct
3 Correct 188 ms 65976 KB Output is correct
4 Correct 161 ms 63676 KB Output is correct
5 Correct 168 ms 54636 KB Output is correct
6 Correct 9 ms 21080 KB Output is correct
7 Correct 188 ms 61368 KB Output is correct
8 Correct 94 ms 32340 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15960 KB Output is correct
2 Correct 19 ms 16388 KB Output is correct
3 Correct 36 ms 16388 KB Output is correct
4 Correct 19 ms 16380 KB Output is correct
5 Correct 36 ms 16188 KB Output is correct
6 Correct 44 ms 16732 KB Output is correct
7 Correct 7 ms 15964 KB Output is correct
8 Correct 36 ms 16652 KB Output is correct
9 Correct 10 ms 16476 KB Output is correct
10 Correct 18 ms 16388 KB Output is correct
11 Correct 7 ms 16472 KB Output is correct
12 Correct 345 ms 16560 KB Output is correct
13 Correct 35 ms 16872 KB Output is correct
14 Correct 35 ms 16872 KB Output is correct
15 Correct 34 ms 16872 KB Output is correct
16 Correct 35 ms 16732 KB Output is correct
17 Correct 22 ms 16476 KB Output is correct
18 Correct 10 ms 16476 KB Output is correct
19 Correct 36 ms 16720 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16220 KB Output is correct
2 Correct 176 ms 61392 KB Output is correct
3 Correct 188 ms 65976 KB Output is correct
4 Correct 161 ms 63676 KB Output is correct
5 Correct 168 ms 54636 KB Output is correct
6 Correct 9 ms 21080 KB Output is correct
7 Correct 188 ms 61368 KB Output is correct
8 Correct 94 ms 32340 KB Output is correct
9 Correct 9 ms 15960 KB Output is correct
10 Correct 19 ms 16388 KB Output is correct
11 Correct 36 ms 16388 KB Output is correct
12 Correct 19 ms 16380 KB Output is correct
13 Correct 36 ms 16188 KB Output is correct
14 Correct 44 ms 16732 KB Output is correct
15 Correct 7 ms 15964 KB Output is correct
16 Correct 36 ms 16652 KB Output is correct
17 Correct 10 ms 16476 KB Output is correct
18 Correct 18 ms 16388 KB Output is correct
19 Correct 7 ms 16472 KB Output is correct
20 Correct 345 ms 16560 KB Output is correct
21 Correct 35 ms 16872 KB Output is correct
22 Correct 35 ms 16872 KB Output is correct
23 Correct 34 ms 16872 KB Output is correct
24 Correct 35 ms 16732 KB Output is correct
25 Correct 22 ms 16476 KB Output is correct
26 Correct 10 ms 16476 KB Output is correct
27 Correct 36 ms 16720 KB Output is correct
28 Execution timed out 2068 ms 67880 KB Time limit exceeded
29 Halted 0 ms 0 KB -