Submission #427468

#	Time	Username	Problem	Language	Result	Execution time	Memory
427468		abdzag	Virus Experiment (JOI19_virus)	C++17	14 / 100	759 ms	192000 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<int>> visited(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);
}
int main() {
	string D;
	cin >> M >> R >> C;
	cin >> D;
	D += D;
	vector<ll> edges(16);
	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;
		}
	}
	vector<vector<ll>> grid(R, vector<ll>(C));
	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]==inf && grid[o][z] != inf) {
				visited[o][z] = ++counter;
				q.emplace(o, z);
				while (!q.empty()) {
					pair<ll, ll> cur = q.front();
					q.pop();
					if (!inside(cur.first, cur.second))continue;
					rep(i, 0, 4) {
						if (inside(cur.first + nexty[i], cur.second + nextx[i])) {
							ll val = 0;
							vector<pair<ll, ll>> addd;
							if (grid[cur.first + nexty[i]][cur.second + nextx[i]] <= edges[1 << ((i + 2) % 4)]) {
								visited[cur.first][cur.second] = min(visited[cur.first][cur.second], visited[cur.first + nexty[i]][cur.second + nextx[i]]);
							}
							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 (visited[x][y]>=visited[cur.first][cur.second]&& visited[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]]==inf) {
								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;
								visited[cur.first + nexty[i]][cur.second + nextx[i]] = ++counter;
								q.emplace(cur.first + nexty[i], cur.second + nextx[i]);
							}
						}

					}

				}
			}
		}

	}
	visited.clear();
	visited.resize(1e3, vector<int>(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<int>(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()) {
		if (cringe[i])continue;
		if (res[i].size() < ans) {
			ans = res[i].size();
		}
		else if (res[i].size() == ans)howmany++;
	}
	cout << ans << endl << ans * howmany << endl;
	return 0;
}

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:197: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]
  197 |   if (res[i].size() < ans) {
      |       ~~~~~~~~~~~~~~^~~~~
virus.cpp:200: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]
  200 |   else if (res[i].size() == ans)howmany++;
      |            ~~~~~~~~~~~~~~^~~~~~

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