Submission #197456

#	Time	Username	Problem	Language	Result	Execution time	Memory
197456		combi1k1	Virus Experiment (JOI19_virus)	C++14	6 / 100	772 ms	262148 KiB

virus

#include <bits/stdc++.h>
using namespace std;
#define count cnt
string s;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const char dir[] = {'E', 'W', 'S', 'N'};

typedef pair <int, int> pii;

bool done[805][805];
bool vis[805][805];
bool infect[1 << 4][805][805];
int a[805][805];
int ans[805][805];
int optimal;
int count;
int r, c;
unordered_set <int> reachable[805][805];

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

    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);

        p[x] = y;

        return  1;
    }
}
inline int convert(int i, int j) {
	return j + i * c;
}
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 <pii> Q;
	vector <pii> reach;
	vis[x][y] = true;
	Q.push(pii(x, y));
	bool bad = false;
	while(!Q.empty()) {
		int p = Q.front().first;
		int q = Q.front().second;
		Q.pop();
		reach.push_back(pii(p, q));
		if(bad) continue;
		for(int i = 0; i < 4; i++) {
			int nx = p + dx[i];
			int ny = q + dy[i];
			if(!valid(nx, ny) || vis[nx][ny]) continue;
			if(check(nx, ny)) {
				int anc = DSU::lead(convert(nx, ny));
				nx = (anc / c);
				ny = (anc % c);
				if(done[nx][ny]) {
					if(ans[nx][ny] == optimal && reachable[nx][ny].find(convert(x, y)) != reachable[nx][ny].end()) {
						++count;
						ans[x][y] = ans[nx][ny];
						DSU::join(convert(x, y), anc);
					} else {
						ans[x][y] = INT_MAX;
					}
					bad = true;
					break;
				}
				Q.push(pii(nx, ny));
				vis[nx][ny] = true;
			}
		}
	}
	for(auto i : reach) {
		vis[i.first][i.second] = false;
	}
	done[x][y] = true;
	if(!bad) {
		ans[x][y] = reach.size();
		if(optimal == ans[x][y]) {
			++count;
		} else if (ans[x][y] < optimal) {
			optimal = ans[x][y];
			count = 1;
		}
  		reachable[x][y].max_load_factor(0.25); //updated !
		for(auto i : reach) {
			reachable[x][y].insert(convert(i.first, i.second));
		}
	}
}
int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n >> r >> c;
	cin >> s;
	s += s;
	for(int x = 0; x < r; x++) {
		for(int y = 0; y < c; y++) {
			cin >> a[x][y];
		}
	}
	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 = INT_MAX;

        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;
	}
	optimal = INT_MAX;
	count = 0;

	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 << optimal << endl;
	cout << count << endl;
	return 0;
}

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:158:37: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     for(int j = 0 ; j < c ; ++j)    if (a[i][j])
                                     ^~
virus.cpp:161:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  cout << optimal << endl;
  ^~~~

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