Submission #1074080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074080		pan	Virus Experiment (JOI19_virus)	C++17	6 / 100	2090 ms	23880 KiB

virus

#include <bits/stdc++.h>
//#include "bits_stdc++.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
using namespace std;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;

ll m, r, c;
ll mapp[805][805];
ll wind[200005];
ll longest[20];

// UFDS

ll hh(ll x, ll y) {return (x)*c + (y);}

ll par[700005];
ll find(ll x) {return ((par[x]==x)?x:par[x] = find(par[x]));}
void unite(ll from, ll to) {par[find(from)] = find(to);}

// BFS

ll dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, 1, -1};
ll fin[805][805], visited[805][805];
vector<pi> minn, now;
ll siz = LLONG_MAX;

bool bfs(ll x, ll y, ll t)
{
	show3(x, y, t);
	now.clear();
	//prevv[hh(x, y)] = t;
	queue<pi> q;
	q.push(mp(x, y));
	while (q.size())
	{
		pi ci = q.front();
		q.pop();
		if (find(hh(ci.f, ci.s)) != find(hh(x, y)))
		{
			//show2(x, y);
			//show2(ci.f, ci.s);
			unite(find(hh(x, y)), find(hh(ci.f, ci.s)));
			//prevv[find(hh(ci.f, ci.s))] = t;
			return 1;
		}
		if (visited[ci.f][ci.s]==t) continue;
		visited[ci.f][ci.s] = t;
		now.pb(mp(ci.f, ci.s));
		for (ll i=0; i<4; ++i)
		{
			ll newx = ci.f + dx[i], newy = ci.s + dy[i];
			if (newx < 0 || newx >= r || newy < 0 || newy >= c || !mapp[newx][newy] || visited[newx][newy]==t) continue;
			ll mask = 0;
			for (ll j=0; j<4; ++j)
			{
				ll newx2 = newx + dx[j], newy2 = newy + dy[j];
				if (newx2 < 0 || newx2 >= r || newy2 < 0 || newy2 >= c || visited[newx2][newy2]!=t) continue;
				mask += (1LL << j);
			}
			if (longest[mask] < mapp[newx][newy]) continue;
			q.push(mp(newx, newy));
		}
	}
	fin[x][y] = 1;
	if (siz > now.size())
	{
		siz = now.size();
		minn = now;
	}
	else if (siz == now.size())
	{
		for (pi u: now) minn.pb(u);
	}
	return 0;
}


int main()
{
	string d;
	cin >> m >> r >> c >> d;
	for (ll i=0; i<r; ++i) for (ll j=0; j<c; ++j) {cin >> mapp[i][j]; par[hh(i, j)] = hh(i, j); visited[i][j] = 0;}
	d = d+ d;
	for (ll i=0; i<2*m; ++i) 
	{
		if (d[i]=='N') wind[i] = 0;
		else if (d[i]=='S') wind[i] = 1;
		else if (d[i]=='E') wind[i] = 2;
		else wind[i] = 3;
	}
	// preprocess edges
	for (ll mask=0; mask< (1LL << 4); ++mask)
	{
		ll idx = 0;
		longest[mask] = 0;
		for (ll i=0; i<2*m; ++i)
		{
			if ((mask & (1LL << wind[i])) == 0) {idx = i+1; }
			longest[mask]  = max(longest[mask], i - idx + 1);
		}
		//show2(mask, longest[mask]);
	}
	for (ll i=1; i<=16; ++i) if (2*m == longest[i]) longest[i] = LLONG_MAX;
	// BFS
	ll t = 0;
	bool done = 1;
	while (done)
	{
		done = 0;
		for (ll i=0; i<r; ++i) for (ll j=0; j<c; ++j)
		{
			if (mapp[i][j] && find(hh(i, j)) == hh(i, j) && !fin[i][j])
			{
				t++;
				done |= bfs(i, j, t);
			}
		}
	}
	cout << siz << endl;
	cout << minn.size() << endl;
	
	
	return 0;
}

Compilation message (stderr)

virus.cpp: In function 'bool bfs(ll, ll, ll)':
virus.cpp:96:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  if (siz > now.size())
      |      ~~~~^~~~~~~~~~~~
virus.cpp:101:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  else if (siz == now.size())
      |           ~~~~^~~~~~~~~~~~~

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