QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#307831#1127. Virus Experiment5ab0 116ms121456kbC++204.6kb2024-01-19 10:33:112024-01-19 10:33:12

Judging History

This is the latest submission verdict.

  • [2024-01-19 10:33:12]
  • Judged
  • Verdict: 0
  • Time: 116ms
  • Memory: 121456kb
  • [2024-01-19 10:33:11]
  • Submitted

answer

/* name: 1127
 * author: 5ab
 * created at: 2024-01-08
 */
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <tuple>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define ssz(x) (int((x).size()))

auto chmax = [](auto& x, auto y) { if (x < y) x = y; };
auto chmin = [](auto& x, auto y) { if (y < x) x = y; };

using ll = long long;
const int max_n = 800, max_nd = max_n * max_n, max_m = 1e5, drs = 4, sdr = 1 << drs, INF = 1145141919;
const char dr[] = "NESW";

int d[max_n][max_n], c[sdr], st[max_nd], ed[max_nd], par[max_nd], ind = 0, mn = INF, mnc = 0;
int dsu[max_nd * (drs + 1)], siz[max_nd * (drs + 1)], cmk[max_nd * (drs + 1)], nm, m;
vector<int> ad[max_nd], g[max_nd];
vector<pair<int, int>> es;
bool vis[max_nd], bd[max_nd];
char s[max_m + 1];

int fnd(int x) { return x == dsu[x] ? x : (dsu[x] = fnd(dsu[x])); }

int gid(char c) {
	return find(dr, dr + drs, c) - dr;
}
void updmsk(int& mk, int d) {
	mk = (mk && d ? mk | d : 0);
}
bool dok(int rx, int x, int y) {
	return c[cmk[rx]] >= d[x][y];
}
void push(int rt, int rx, int x, int y)
{
	// cerr << rt << " " << x << " " << y << " " << cmk[rx] << " " << c[cmk[rx]] << endl;
	dsu[rx] = rt;
	ad[rt].push_back(rx);
	if (dok(rx, x, y))
		g[rt].push_back(rx);
}

void dfs(int id)
{
	st[id] = ind++, vis[id] = 1;
	// cerr << id << endl;
	while (!g[id].empty())
	{
		int dst = g[id].back() % nm;
		// cerr << id << " " << dst << endl;
		g[id].pop_back();
		
		// if (fnd(dst) == fnd(id))
		// 	continue;
		es.emplace_back(id, dst);
		if (!vis[dst])
		{
			// cerr << id << " --> " << dst << endl;
			par[dst] = id;
			dfs(dst);
			continue;
		}
		if (!(st[fnd(dst)] <= st[id] && ed[id] <= ed[fnd(dst)]))
			continue;
		// cerr << dst << " " << id << endl;
		while (fnd(dst) != fnd(id))
		{
			int x = fnd(id), y = fnd(par[x]), inv = 0;
			if (ssz(ad[y]) < ssz(ad[x]))
				swap(ad[x], ad[y]), swap(g[x], g[y]), swap(x, y), inv = 1;
			g[x].clear();
			for (auto p : ad[x])
				dsu[p] = p;
			for (auto p : ad[x])
			{
				int rx = p % nm, cx = rx / m, cy = rx % m;
				bool ok = 1;
				for (int i = 0, tx = rx; i <= drs; i++, tx += nm)
					if (fnd(tx) == y)
					{
						ok = 0;
						bool pok = dok(tx, cx, cy);
						// cerr << "> " << cmk[tx] << " " << cx << " " << cy << endl;
						updmsk(cmk[tx], cmk[p]);
						if (dok(tx, cx, cy) && !pok)
							g[y].push_back(tx);
						break;
					}
				if (ok)
					push(y, p, cx, cy);
			}
			ad[x].clear();
			if (inv)
				swap(x, y), swap(ad[x], ad[y]), swap(g[x], g[y]);
			dsu[x] = y, siz[y] += siz[x];
		}
		// cerr << "? " << fnd(id) << endl;
		// for (auto p : g[fnd(id)])
		// 	cerr << p % nm << " ";
		// cerr << endl;
	}
	ed[id] = ind;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, sl;
	
	cin >> sl >> n >> m >> s;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			cin >> d[i][j];
			if (d[i][j] == 0)
				d[i][j] = INF;
		}
	nm = n * m;
	
	for (int i = 0; i < sdr; i++)
	{
		int j = 0;
		for (; j < sl && ((i >> gid(s[j])) & 1); j++);
		if (j == sl)
		{
			c[i] = INF - 1;
			continue;
		}
		c[i] = j;
		int sp = j, k = j;
		// cerr << "??? " << i << " " << j << endl;
		while  (k < sl)
		{
			for (j = k; j < sl && !((i >> gid(s[j])) & 1); j++);
			for (k = j; k < sl && ((i >> gid(s[k])) & 1); k++);
			// cerr << j << " " << k << endl;
			chmax(c[i], k - j);
		}
		chmax(c[i], k - j + sp);
		// cerr << i << " " << c[i] << endl;
	}
	
	for (int i = 0, x = 0; i < n; i++)
		for (int j = 0; j < m; j++, x++)
			for (int k = 0, tx = x + nm; k < drs; k++, tx += nm)
				cmk[tx] = (1 << k);
	
	iota(dsu, dsu + n * m * (drs + 1), 0);
	fill(siz, siz + n * m, 1);
	for (int i = 0, x = 0; i < n; i++)
		for (int j = 0; j < m; j++, x++)
		{
			if (i < n - 1) push(x, x + m + nm, i + 1, j);
			if (j) push(x, x - 1 + nm * 2, i, j - 1);
			if (i) push(x, x - m + nm * 3, i - 1, j);
			if (j < m - 1) push(x, x + 1 + nm * 4, i, j + 1);
		}
	
	fill(ed, ed + n * m, INF);
	for (int i = 0, x = 0; i < n; i++)
		for (int j = 0; j < m; j++, x++) if (!vis[x] && d[i][j] != INF)
			dfs(x);
	for (auto [x, y] : es)
		if (fnd(x) != fnd(y))
			bd[fnd(x)] = 1;
	for (int i = 0, x = 0; i < n; i++)
		for (int j = 0; j < m; j++, x++)
			if (d[i][j] != INF && !bd[fnd(x)])
			{
				int id = fnd(x);
				// cerr << i << " " << j << endl;
				if (siz[id] < mn)
					mn = siz[id], mnc = 1;
				else if (siz[id] == mn)
					mnc++;
			}
	cout << mn << "\n" << mnc << endl;
	
	return 0;
}
// started coding at: 01-08 22:03:13

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 14
Accepted
time: 5ms
memory: 16068kb

input:

53768 10 50
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

1
10

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 116ms
memory: 111948kb

input:

10 800 800
WWWWEWWEWW
7 3 7 5 10 6 9 6 5 8 1 10 1 6 6 1 8 9 3 7 1 3 1 4 9 3 4 2 5 4 5 7 8 10 4 6 2 8 7 2 1 5 3 10 9 10 1 7 6 2 1 8 3 4 10 5 3 3 3 9 2 2 6 1 6 5 6 3 7 9 7 5 8 5 4 3 7 6 9 3 4 9 1 2 7 1 3 4 6 10 8 4 4 9 1 2 6 1 4 4 10 6 10 4 1 5 1 8 5 2 1 9 4 10 9 2 7 9 4 1 6 5 1 6 6 10 10 1 3 10 6 4 8...

output:

1
230450

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 112ms
memory: 121456kb

input:

10 800 800
WWWWWWWWWW
15314 11896 14475 25269 31478 32227 37443 24837 1353 32232 8163 3206 34713 17755 6870 20331 29572 19341 12557 36054 14768 990 30502 32464 15439 17070 15514 32216 37546 25514 27706 3028 26652 17247 13171 40866 36133 9550 22005 24048 33764 25331 12936 27462 27217 33096 19096 3919...

output:

1
800

result:

ok 2 lines

Test #4:

score: 0
Accepted
time: 95ms
memory: 119176kb

input:

31 800 800
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

1
800

result:

ok 2 lines

Test #5:

score: 0
Accepted
time: 75ms
memory: 79308kb

input:

9999 800 800
WWWEEWEEWEWEEEWEEEWWWEWWEEEEEWEEEWWEWWWEWEWEWEEEWWWWWEWEEEEEEWEEWWEWWEEEEWEWWEWWWEEEWWEEWEWWWEWWEWWEEEWWWEWEEWWEWEWWWEWWWEEEWWEEEWWEEEWWWWEWWEWEWWWWEEWEEEWEWWEWEEWEWEEEWEWEEEWWWWEEEEWWWWWWEWWWEWEWWWEWEWWWEWWEEEEWWEEEEEWEWEWWWEWEEEEWEEEEWEEWEEEEEWEWWEEEWWEEEWEEEEWWEWWEEWEEWEWWEWWWEWEEEWE...

output:

1
639810

result:

ok 2 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 17912kb

input:

10 800 1
EWEWWWWWWW
1
1
1
0
1
0
0
0
1
0
0
0
1
1
1
0
0
0
0
1
0
0
0
0
0
0
1
1
0
1
1
0
0
1
1
0
1
0
1
0
0
0
0
1
1
1
1
1
0
0
1
1
0
1
0
0
0
1
0
0
0
1
0
1
1
0
1
1
0
1
1
1
0
0
0
0
1
1
0
1
0
1
0
0
1
0
0
0
1
1
1
1
0
0
1
1
1
1
0
0
1
0
0
1
1
1
0
1
0
1
0
1
0
1
0
1
0
0
0
1
1
0
0
1
1
1
0
0
1
1
0
0
1
1
1
1
1
1
1
0
...

output:

1
392

result:

ok 2 lines

Test #7:

score: -14
Time Limit Exceeded

input:

100000 800 800
WWEEWEEWEEEWEEWWWWWEEEWWWEEEWEWWEWEEEWWWEEEWEWWWWEEWWEWEEEEEEWWEEEWWWWWWWEWWWEEWWWWWWEEWEWEWEEWEWEWEWWEEEEWEEEEWEWWWWEEEEWWWEWWWEWWEWEWWWEWEWEWWEEEEEEWEEEEEWEEEEEWEEEWEEEEEEEWEWWWEWWWEWWWWEEWWEWEEEWWWWEEEEEEWWWEEEEEWEWEWWEWEEEEEEEWEEWWEWWEEWWEEEEEWWEWEWEEWWEEWEEWEWWWWEEWEWEWEEEEEEEWEW...

output:


result:


Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 6
Accepted
time: 0ms
memory: 15888kb

input:

10 10 10
NNNNSENESS
3 2 0 0 1 3 2 3 1 2
3 3 2 0 5 2 4 0 5 1
5 1 2 3 0 4 4 0 1 0
5 0 1 0 2 4 2 2 0 3
0 1 0 1 4 0 1 4 1 0
3 5 5 0 2 5 3 0 3 4
5 3 1 0 5 4 4 0 4 4
1 0 2 0 5 4 0 2 3 0
4 2 0 2 3 0 2 5 5 4
3 0 2 0 5 4 5 4 0 5

output:

1
33

result:

ok 2 lines

Test #10:

score: 0
Accepted
time: 2ms
memory: 16016kb

input:

100000 10 10
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...

output:

1
10

result:

ok 2 lines

Test #11:

score: 0
Accepted
time: 14ms
memory: 16116kb

input:

100000 11 11
SWNESSSWNSEWNSNESSNWEWEWNSNNSWSSWSEEWNENWSWNNEWWSWNSESSEWENNESSENEEEESEESEWENEWSNSNNSSNNSWSNNSNESWEWSENNSESEEWWNESSNNWWSNWNNWNWNWWSEENNNWESSWNWNSEWWNWNNWSWSEWSENSNWNWNNEESSSENWWESSWEESWWENSSENWNNEESWENWSSSWEEWNWEWNNENNWSWEWSNNEESESNWNSEEENWWESSWEEWWSWESSNNEEWWNSSWSNEWSENSNNSENNSSNSSEEEE...

output:

27
27

result:

ok 2 lines

Test #12:

score: 0
Accepted
time: 5ms
memory: 16008kb

input:

100000 10 10
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

1
16

result:

ok 2 lines

Test #13:

score: 0
Accepted
time: 18ms
memory: 15984kb

input:

100000 1 1
WWSSSWEEEEESSNSSSSENWSESSNSWWSWESWSEEWSNSSEESSWESNNNENENWEENSSSSSNENESEESEWWSNNWSEWSWNWESSWNWSEESNSWSWENWEWNWESEWSSNSWENEWNNSWEEWWSSSWNSNWWWNSSWSSNSENESENNNENWESSENNEWENWEENWNWSSSWWWSNWESWEESNNNESNNEESNEWSSNNSSWSSESNSNNWENENEWWWSEESNWEWWNWNNSSNEEWSWNSWEESNSNSNEWNNWWWWSSWSWWESWWENSENWNWNWN...

output:

1
1

result:

ok 2 lines

Test #14:

score: 0
Accepted
time: 19ms
memory: 16536kb

input:

100000 50 50
ENWNNWEESNSNSSESSWNEWWESNWEENNEEWWEWNNESSSEWSWNWEWSSNEEWNSEWSSWNESWSWESEWWSENEWESEWSWSNNWWESSSWSSSESESNSSNESSSWSNWSSSENSWWNWNWNNNSNSNSEENWESENEENNESENSENNWEEESENWSESWSNWNNNSNSNWWENWEEEWSNWWEWSWNSEEEWEWWNSWNNNWWENSNSWWSNNWESNSSSWWNSEWSNWNEEESSEWEESENEESWSNNWSNESEESWEESNWSEEWWSSWESENESSSE...

output:

2500
2500

result:

ok 2 lines

Test #15:

score: 0
Accepted
time: 0ms
memory: 15944kb

input:

100 10 10
NENNWNSNNEWNENENNWWNEWNSNWWSSSNSNESSESWESSNNNNEWSWESNSNWSENWNSESNENWSWEWWWNSNWNWESNSESENNWNNWSSWSNSE
2 1 4 1 4 2 1 3 2 4
1 4 4 4 3 3 4 2 2 1
1 3 1 4 2 2 1 4 2 2
2 3 4 3 3 3 1 2 4 1
2 2 3 4 3 4 4 1 3 4
1 4 4 3 4 4 1 4 4 2
1 4 3 4 1 1 3 3 4 3
4 4 1 2 3 3 2 3 4 4
2 4 2 1 1 3 4 2 4 4
2 1 2 3 4...

output:

1
1

result:

ok 2 lines

Test #16:

score: -6
Wrong Answer
time: 14ms
memory: 15980kb

input:

100000 50 2
ESNNNSWNNESEWSWWWSENWENSWSNSENSWSENWWNEENNWWNESWNWSEWSWWNSSWSSNENSWWWEEEEENSNWWNNESEWSSNSEEENWWNWWNEENSENWSWEWWNNWWNESSSNWNWWSEWEESESNEEEWNNWWEEEESWSEWWNNSNENWWSEEWNWSNWWEEWNSNWWWWWNWWNNSENNEWSEWENSSSSNWSSSNWSNSNEWESEESWWSEEWWWNWWNESNSNSSNEEWSSENNNEEENSNEEEESNSWNNESEENNEESNSSWENSWSWSNSEE...

output:

42
42

result:

wrong answer 1st lines differ - expected: '46', found: '42'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%