Submission #427687

#	Time	Username	Problem	Language	Result	Execution time	Memory
427687		abdzag	Virus Experiment (JOI19_virus)	C++17	14 / 100	678 ms	191844 KiB

virus

#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define trav(a,v) for(auto& a: v)
#define sz(v) v.size()
#define all(v) v.begin(),v.end()
#define vi vector<int>

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const long long inf = 2e9;

using namespace std;
int dc[4] = { 'N', 'W', 'S', 'E' };
int nexty[4] = { -1, 0, 1, 0 };
int nextx[4] = { 0, -1, 0, 1 };
int M, R, C;
bool inside(int y, int x) {
	return 0 <= y && y < R && 0 <= x && x < C;
}

bool inmax(ll& a, int b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}

int ctod(char c) {
	for (int i = 0; i < 4; i++) {
		if (c == dc[i]) return i;
	}
	return -1;
}
vector<vector<vector<pair<ll, ll>>>> g(1000, vector<vector<pair<ll, ll>>>(1000));
vector<pair<ll, ll>> v;
vector<vector<bool>> visited(1e3, vector<bool>(1e3));
vector<vector<int>> disc(1e3, vector<int>(1e3, inf));
vector<vector<vector<pair<ll, ll>>>> g2(1000, vector<vector<pair<ll, ll>>>(1000));
void dfs(pair<ll, ll> cur) {
	visited[cur.first][cur.second] = 1;
	trav(a, g[cur.first][cur.second]) {
		if (!visited[a.first][a.second])dfs(a);
	}
	v.push_back(cur);
}
set<pair<ll, ll>> temp;
void dfs2(pair<ll, ll> cur) {
	visited[cur.first][cur.second] = 1;
	trav(a, g2[cur.first][cur.second]) {
		if (!visited[a.first][a.second]) {
			//cout << "from " << cur.first << " " << cur.second << " to " << a.first << " " << a.second << endl;
			dfs2(a);
		}
	}
	temp.insert(cur);
}
vector<vector<ll>> grid(1e3, vector<ll>(1e3));

vector<ll> edges(16);
ll counter = 0;
void dfs3(pair<ll, ll> cur) {
	if (grid[cur.first][cur.second] == inf)return;
	if (visited[cur.first][cur.second])return;
	visited[cur.first][cur.second] = 1;
	disc[cur.first][cur.second] = ++counter;
	if (!inside(cur.first, cur.second))return;
	rep(i, 0, 4) {
		if (inside(cur.first + nexty[i], cur.second + nextx[i])) {
			if (grid[cur.first + nexty[i]][cur.second + nextx[i]] <= edges[1 << ((i + 2) % 4)]) {
				dfs3(make_pair(cur.first + nexty[i], cur.second + nextx[i]));
				disc[cur.first][cur.second] = min(disc[cur.first][cur.second], disc[cur.first + nexty[i]][cur.second + nextx[i]]);
			}
		}
	}
	rep(i, 0, 4) {
		if (inside(cur.first + nexty[i], cur.second + nextx[i])) {
			ll val = 0;
			vector<pair<ll, ll>> addd;
			rep(j, 0, 4) {
				ll x = cur.first + nexty[i] + nexty[j];
				ll y = cur.second + nextx[i] + nextx[j];
				if (inside(x, y)) {
					if (disc[x][y] >= disc[cur.first][cur.second] && disc[x][y] != inf) {
						val = val | (1 << j);
					}

				}
			}
			bool done = true;
			trav(b, g[cur.first][cur.second]) {
				if (b == make_pair(cur.first + nexty[i], cur.second + nextx[i])) {
					done = false;
				}
			}
			if (done && edges[val] >= grid[cur.first + nexty[i]][cur.second + nextx[i]])g[cur.first][cur.second].push_back(make_pair(cur.first + nexty[i], cur.second + nextx[i]));
			if (visited[cur.first + nexty[i]][cur.second + nextx[i]] == 0) {
				bool done = true;
				trav(a, g[cur.first][cur.second])if (a == make_pair(cur.first + nexty[i], cur.second + nextx[i]))done = false;
				if (done)continue;
				dfs3(make_pair(cur.first + nexty[i], cur.second + nextx[i]));
				disc[cur.first][cur.second] = min(disc[cur.first][cur.second], disc[cur.first + nexty[i]][cur.second + nextx[i]]);
			}
		}

	}

}
int main() {
	string D;
	cin >> M >> R >> C;
	cin >> D;
	D += D;
	vector<ll> curr(16);
	for (int i = 0; i < M * 2; i++) {
		int d = ctod(D[i]);
		for (int j = 0; j < (1 << 4); j++) {
			if ((j) & 1 << d) {
				curr[j]++;
			}
			else {
				inmax(edges[j], curr[j]);
				curr[j] = 0;
			}
		}
	}
	for (int j = 0; j < (1 << 4); j++) {
		if (curr[j] == M * 2) {
			edges[j] = 1e7;
		}
	}
	rep(i, 0, R) {
		rep(j, 0, C) {
			cin >> grid[i][j];
			if (grid[i][j] == 0)grid[i][j] = inf;
		}
	}
	queue<pair<ll, ll>> q;
	ll counter = 0;
	rep(o, 0, R) {
		rep(z, 0, C) {
			if (visited[o][z] == 0 && grid[o][z] != inf) {
				dfs3(make_pair(o, z));
			}
		}

	}
	visited.clear();
	visited.resize(1e3, vector<bool>(1e3));
	rep(i, 0, R) {
		rep(j, 0, C) {
			if (!visited[i][j])dfs(make_pair(i, j));
		}
	}
	rep(i, 0, R) {
		rep(j, 0, C) {
			trav(a, g[i][j]) {
				g2[a.first][a.second].push_back(make_pair(i, j));
			}
		}

	}
	//cout << "here is your v" << endl;
	//trav(a, v)cout << a.first << " " << a.second << "  ";;
	//cout << endl;
	reverse(all(v));
	//cout << "here is your v" << endl;
	//trav(a, v)cout << a.first << " " << a.second << "  ";;
	//cout << endl;
	visited.clear();
	visited.resize(1e3, vector<bool>(1e3));
	vector<set<pair<ll, ll>>> res;
	rep(i, 0, v.size()) {
		temp.clear();
		if (!visited[v[i].first][v[i].second] && grid[v[i].first][v[i].second] != inf)dfs2(v[i]);
		if (temp.size())res.push_back(temp);
	}
	ll ans = inf;
	ll howmany = 1;
	//cout << "here are your components" << endl;
	//trav(vec, res) {
	//	trav(a, vec)cout << a.first << " "<<a.second<<"   ";
	//	cout << endl;
	//}
	//rep(i, 0, R) {
	//	rep(j, 0, C) {
	//		cout << "cur: " << i << " " << j << endl;
	//		trav(a, g[i][j])cout << a.first << " " << a.second << "  ";
	//		cout << endl;
	//	}
	//}
	vector<bool> cringe(res.size());
	rep(i, 0, res.size()) {
		trav(a, res[i]) {
			trav(cur, g[a.first][a.second]) {
				if (res[i].find(cur) == res[i].end())cringe[i] = 1;
			}
		}
	}

	rep(i, 0, res.size()) {
		//trav(a, res[i])cout << a.first << " " << a.second << "  ";
		//cout << endl;
		if (cringe[i])continue;
		//if (res[i].size() == 1)cout << (*res[i].begin()).first<<" "<<(*res[i].begin()).second<<endl;
		//cout << "based" << endl;
		if (res[i].size() < ans) {
			ans = res[i].size();
			howmany = 1;
		}
		else if (res[i].size() == ans) {
			howmany++;
		}
	}
	ll var = -1;
	cout << ans << endl << ans * howmany << endl;
	return 0;
}

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:211:21: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  211 |   if (res[i].size() < ans) {
      |       ~~~~~~~~~~~~~~^~~~~
virus.cpp:215:26: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  215 |   else if (res[i].size() == ans) {
      |            ~~~~~~~~~~~~~~^~~~~~
virus.cpp:143:5: warning: unused variable 'counter' [-Wunused-variable]
  143 |  ll counter = 0;
      |     ^~~~~~~
virus.cpp:219:5: warning: unused variable 'var' [-Wunused-variable]
  219 |  ll var = -1;
      |     ^~~

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