Submission #197455

#	Time	Username	Problem	Language	Result	Execution time	Memory
197455		combi1k1	Virus Experiment (JOI19_virus)	C++14	0 / 100	759 ms	262148 KiB

virus

#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 805;
const int   inf = 1e9;

namespace DSU   {
    int p[N * N];
    int s[N * N];

    int init(int n) {
        iota(p,p + n,0);
        fill(s,s + n,1);
        return  1;
    }
    int lead(int x) {
        return p[x] == x ? x : p[x] = lead(p[x]);
    }
    int join(int x,int y)   {
        x = lead(x);
        y = lead(y);

        return  p[x] = y;
    }
}

typedef pair<int,int>   ii;

int dx[] = {0,  0, 1, -1};
int dy[] = {1, -1, 0,  0};
char dir[] = {'E','W','S','N'};

bool cal[N][N];
bool vis[N][N];
bool infect[16][N][N];

int a[N][N];
int R, C;

int ans[N][N];
int res = inf;
int cnt = 0;

unordered_set<int>  reachable[N][N];

inline int valid(int x,int y)   {
    if (x < 0 || x >= R)    return  0;
    if (y < 0 || y >= C)    return  0;
    return  1;
}
inline int check(int x,int y)   {
    int mask = 0;
    for(int i = 0 ; i < 4 ; ++i)    {
        int xx = x + dx[i];
        int yy = y + dy[i];

        if (valid(xx,yy) && vis[xx][yy])
            mask |= (1 << i);
    }
	return  infect[mask][x][y];
}
void solve(int x,int y) {
    queue <ii>  qu;
    vector<ii>  tour;

    vis[x][y] = 1;  qu.push(ii(x,y));
    bool bad = 0;

    while (qu.size())   {
        int x = qu.front().X;
        int y = qu.front().Y;

        tour.pb(qu.front());    qu.pop();

        if (bad)    continue;

        for(int i = 0 ; i < 4 ; ++i)    {
            int xx = x + dx[i];
            int yy = y + dy[i];

            if(!valid(xx,yy) || vis[xx][yy])    continue;
            if (check(xx,yy))   {
                int num = DSU::lead(xx * C + yy);
                xx = num / C;
                yy = num % C;
                if (cal[xx][yy])   {
                    if (ans[xx][yy] == res && reachable[xx][yy].find(x * C + y) != reachable[xx][yy].end()) {
                        cnt++;
                        ans[x][y] = res;
                        DSU::join(x * C + y,num);
                    }
                    else    ans[x][y] = inf;

                    bad = 1;
                    break;
				}
				qu.push(ii(xx,yy));
				vis[xx][yy] = 1;
			}
		}
	}
	for(ii  C : tour)
        vis[C.X][C.Y] = 0;

    cal[x][y] = 1;

    if(!bad)    {
        ans[x][y] = sz(tour);
        if (res > ans[x][y])
            res = ans[x][y],
            cnt = 0;
        if (res == ans[x][y])
            cnt++;

        reachable[x][y].max_load_factor(0.25);

        for(ii  T : tour)
            reachable[x][y].insert(T.X * C + T.Y);
    }
}

int main()  {
	ios_base:: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;      cin >> n >> R >> C;
	string S;   cin >> S;   S += S;

	for(int i = 0 ; i < R ; ++i)
    for(int j = 0 ; j < C ; ++j)    cin >> a[i][j];

    for(int m = 0 ; m < 16 ; ++m)   {
		int opt = 0;
		int cur = 0;
		for(char c : S) {
            bool have = 0;

            for(int i = 0 ; i < 4 ; ++i)    if (m >> i & 1)
                if (c == dir[i])    {
                    have = 1;
                    break;
                }
            if (have)   cur++;
            else        cur = 0;

            opt = max(cur,opt);
		}
		if (opt == n + n)
            opt = inf;

        for(int i = 0 ; i < R ; ++i)
        for(int j = 0 ; j < C ; ++j)
            if (a[i][j] && a[i][j] <= opt)
                infect[m][i][j] = 1;
	}

    DSU::init(R * C);

    for(int i = 0 ; i < R ; ++i)
    for(int j = 0 ; j < C ; ++j)    if (a[i][j])
        solve(i,j);

    cout << res << "\n";
    cout << cnt << endl;
}
/*
6 3 4
SWNEES
2 1 1 2
1 0 1 3
1 1 2 2
*/

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