Submission #425801

#	Time	Username	Problem	Language	Result	Execution time	Memory
425801		abdzag	Virus Experiment (JOI19_virus)	C++17	14 / 100	983 ms	10772 KiB

virus

#include<bits/stdc++.h>
#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 = 1e15;

using namespace std;
vector<vector<ll>> grid;
vector<vector<ll>> dp;
ll m, r, c;
vector<vector<bool>> visited(1000, vector<bool>(1000));
vector<ll> edges(4);
ll dfs(ll x, ll y, bool first) {
	if (first && grid[x][y] == inf)return inf;
	if (y && first)if (grid[x][y - 1] <= edges[2])return inf;
	if (y == c - 1)return 1;
	if (grid[x][y + 1] <= edges[0])return 1 + dfs(x, y + 1, 0);
	else if (grid[x][y] <= edges[2])return 1;
	return 1;
}
int main() {
	string s;
	cin >> m >> r >> c;
	cin >> s;
	grid.resize(r, vector<ll>(c));
	dp.resize(r, vector<ll>(c, -1));
	rep(i, 0, r) {
		rep(j, 0, c) {
			cin >> grid[i][j];
			if (grid[i][j] == 0)grid[i][j] = inf;
		}
	}
	s += s;
	bool done = true;
	rep(i, 1, s.size())if (s[i] != s[0])done = false;
	map<char, ll> mp;
	mp['W'] = 0;
	mp['N'] = 1;
	mp['E'] = 2;
	mp['S'] = 3;
	ll curchar = -1;
	ll cur = 0;
	if (done)edges[mp[s[0]]] = 1e5;
	rep(i, 0, s.size()) {
		if (curchar != mp[s[i]]) {
			if (curchar != -1)edges[curchar] = max(edges[curchar], cur);
			cur = 0;
			curchar = mp[s[i]];
		}
		cur++;
	}
	//if there is an undirected edge between two nodes and merge them
	//else take the node with that lacks an edge back
	//if tere is no edges between two nodes then you have two different components, take the minimun of them
	//after doing BFS in a compononet you may be able to add nodes , this may be a bit hard to implement
	//the second answer is gonna be the number of nodes in a component
	ll ans = inf;
	ll howmany = 0;
	rep(i, 0, r) {
		rep(j, 0, c) {
			if (ans > dfs(i, j, 1)) {
				ans = min(ans, dfs(i, j, 1));
				howmany = 1;
			}
			else if (ans == dfs(i, j, 1))howmany++;
		}
	}
	cout << ans << endl << ans * howmany << endl;
	return 0;
}

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