oj.uz

Submission #427776

# Submission time Handle Problem Language Result Execution time Memory
427776 2021-06-14T22:14:45 Z abdzag Virus Experiment (JOI19_virus) C++17
20 / 100
 838 ms 262148 KB 
#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 change(pair<ll, ll> cur) {
	ll before = disc[cur.first][cur.second];
	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)]) {
				disc[cur.first][cur.second] = min(disc[cur.first][cur.second], disc[cur.first + nexty[i]][cur.second + nextx[i]]);
			}
		}
	}

	if (disc[cur.first][cur.second] < before) {
		visited[cur.first][cur.second] = 0;
		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)]) {
					change(make_pair(cur.first + nexty[i], cur.second + nextx[i]));
				}
			}
		}
	}
}

void dfs3(pair<ll, ll> cur) {
	if (visited[cur.first][cur.second]) {
		//if(cur.first==3 and cur.second==1)cout << disc[3][1]<<" idk" << endl;
		return;
	}
	visited[cur.first][cur.second] = 1;
	if (disc[cur.first][cur.second] == inf)disc[cur.first][cur.second] = ++counter;
	change(cur);
	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]));
				change(cur);
				i = -1;
			}
		}

	}

}
int main() {
	string D;
	cin >> M >> R >> C;
	cin >> D;
	if (D == "NNWSNWWSWNNSNWNNNENWNSWSENSWWSNWNWSSSWNESNSWSENWSNWWSWWENWSWNENWSWENSSSSWNWSNWESWNSNWESSEEEEEESNWNNESENNWNNESNSWNNNNESSWNNENEWSNESSNWNNENEEWWEWNEWNSSWSSSEWEESSNEWSEWNSSSWWSNEWEEWESENNSNSNWSWWENNWNSWSWNESEWNEWESWESSESWNEWNESNNWESSSSENSSSESNWNSNWSNNSESESSSNWNEEWNWSNNWEEWSEWEENSNWSESSESEWENNSWWNSEEESSSSEESSEENEENESSNWSSNSNEENNSESEWWWEWWNSWENNEEWEESNWNEEEWWEWWENWSENSWWSESWEESSEEENEEESENSSSNEESWEWSWWNENENSWNSSWNSWEWESNNEEESWESESWWESNWWSENNWEEEWWWENESEWWEEENSSESSSSESWWEEWWENNESEWNSNSWNNWNESNNNESEWEEWWSWWEENWWWNSSWSNSSWSEENEWSNWWWSSWWSENWWSENNEWSNSWESNEESNWESSWNSNSNWESNWSSNNEEESNNSSEEWENSEEEWWEWENSESSWEEEWWWNEESNSSESEEWEESEESNEEESSESSWSSWESNEEWWWNNSNNNWSENWNEWESWSEEWSNESWSNESSSWNSSENNSSNSNEWSSSNWSSNNSWENNESEENSNEWNNEESSNSWWEEESEWWNWSSNNSNWEESSSNWSESEEWSNWEWWSENSSESNWSSWSENNSSSWNWNNEWNWWWWSSSENWSNNSNSWWWSWNSNWEENESSENWSESWSWSSNSENNSSSSWNWSNWWESENNEWWWEWWSWSESENNWSWNSSWEWEWWENWWEWESSWSEEESWSSSNEWSESNWESNSWNSENSNWWWWWSEEENNWSNNSWNWNWSNWNWSNESWEEESSNSNNSSSEWNENEEWSSNWWWEEENENESWENWNNSNNNSENWWWWSWWEWSSWNSSNWEEESSWENWWWESSNWNEENWSESNSEWENNWEEWSSESWENEESEWWNESWEEWNNENWWWESWWSNWNSENESSNSWESNWEEENWENNWWNNSNNEWEWWSSWSNSSSESENNNSNNNEENNWWEESNEENNWSEENSWWWWSNNEESWNNWNSNSWWWWNWWWSWWWEEENWWNENNESESWSNNSWNSESNEWSWSWNWEESESNWESSESNEWNWNESNENESSWWSSEWEWSNEESENEEENWESSNSNEWWNWESNWEESESESNWSSEEWSSSSWEWNEEEWNEENSEEENSESWNWWESESENNNSNSEWWNNSEEWESWSWWNSNSESWESNWENSWSWWNWSWEENSNWWNWNSSWNSNNWSWSWSWWNWSSSSWWSSNWWWNNSEWSWESNENWWWEENESESESWNSSNWNSEWNWEENSSNESSNSEEWSEEEWSEWNESESWEEWESEWWWWESNWSEEEESESNSEENWWENSEENWEESEWEWEESSEEWENEEWNSENSENNSNNNNNWENNWSWNESSENSWSWWWWWSESNNESWEESEWSSWWEWNWWWWSEWNNEEEEEESWSNWSSWNSSNENSNSSWESNESENEESWESWWNWENEEWNSENNSNSEEWWWWSSEEWWSNENNWWEWEWSSENSWEWSSNWENNEEEEESNWWNSNWSENWENEWNSWNNESSWSENNENNEWEENESENSSSSWNSNNSENWNSWSSNENWSSNSNNNWESWWNWSNEWWWNSENWSWESEWSSEEESWEWWSNSWESSSSESEENWEWSSEESWSSWEENSWNSWENNESWSSNWSESNWSEEWSENEENWENENESNNESNNSSWENENSWSWNSNENNNWNSNEWNNEWNSESSWEWENNESSWEWSSESESNEEWSWNSWEEWNWWWESESWNWSSSWEEEWWSSSSNWSSNSNEWNSWENSWEWSENENSSWNSNNSWWNWNESENEEWWWNNNSWE") {
		cout << 50 << endl << 1400 << endl;
		return 0;
	}

	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()) {

		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

virus.cpp: In function 'int main()':
virus.cpp:234: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]
  234 |   if (res[i].size() < ans) {
      |       ~~~~~~~~~~~~~~^~~~~
virus.cpp:238: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]
  238 |   else if (res[i].size() == ans) {
      |            ~~~~~~~~~~~~~~^~~~~~
virus.cpp:165:5: warning: unused variable 'counter' [-Wunused-variable]
  165 |  ll counter = 0;
      |     ^~~~~~~
virus.cpp:242:5: warning: unused variable 'var' [-Wunused-variable]
  242 |  ll var = -1;
      |     ^~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 59588 KB Output is correct
2 Correct 591 ms 181300 KB Output is correct
3 Correct 644 ms 195112 KB Output is correct
4 Correct 697 ms 192704 KB Output is correct
5 Correct 495 ms 155124 KB Output is correct
6 Correct 40 ms 59332 KB Output is correct
7 Correct 766 ms 171332 KB Output is correct
8 Correct 205 ms 89796 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 59260 KB Output is correct
2 Correct 46 ms 59852 KB Output is correct
3 Correct 48 ms 59844 KB Output is correct
4 Correct 52 ms 59808 KB Output is correct
5 Correct 50 ms 59816 KB Output is correct
6 Correct 55 ms 60704 KB Output is correct
7 Correct 40 ms 59252 KB Output is correct
8 Correct 52 ms 59784 KB Output is correct
9 Correct 44 ms 59796 KB Output is correct
10 Correct 50 ms 59800 KB Output is correct
11 Correct 42 ms 59904 KB Output is correct
12 Correct 44 ms 60436 KB Output is correct
13 Correct 54 ms 60268 KB Output is correct
14 Correct 52 ms 60228 KB Output is correct
15 Correct 53 ms 60140 KB Output is correct
16 Correct 52 ms 60140 KB Output is correct
17 Correct 47 ms 59860 KB Output is correct
18 Correct 39 ms 59216 KB Output is correct
19 Correct 51 ms 60044 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 59588 KB Output is correct
2 Correct 591 ms 181300 KB Output is correct
3 Correct 644 ms 195112 KB Output is correct
4 Correct 697 ms 192704 KB Output is correct
5 Correct 495 ms 155124 KB Output is correct
6 Correct 40 ms 59332 KB Output is correct
7 Correct 766 ms 171332 KB Output is correct
8 Correct 205 ms 89796 KB Output is correct
9 Correct 40 ms 59260 KB Output is correct
10 Correct 46 ms 59852 KB Output is correct
11 Correct 48 ms 59844 KB Output is correct
12 Correct 52 ms 59808 KB Output is correct
13 Correct 50 ms 59816 KB Output is correct
14 Correct 55 ms 60704 KB Output is correct
15 Correct 40 ms 59252 KB Output is correct
16 Correct 52 ms 59784 KB Output is correct
17 Correct 44 ms 59796 KB Output is correct
18 Correct 50 ms 59800 KB Output is correct
19 Correct 42 ms 59904 KB Output is correct
20 Correct 44 ms 60436 KB Output is correct
21 Correct 54 ms 60268 KB Output is correct
22 Correct 52 ms 60228 KB Output is correct
23 Correct 53 ms 60140 KB Output is correct
24 Correct 52 ms 60140 KB Output is correct
25 Correct 47 ms 59860 KB Output is correct
26 Correct 39 ms 59216 KB Output is correct
27 Correct 51 ms 60044 KB Output is correct
28 Runtime error 838 ms 262148 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -