Submission #915188

#	Time	Username	Problem	Language	Result	Execution time	Memory
915188		qin	Virus Experiment (JOI19_virus)	C++17	0 / 100	129 ms	26892 KiB

virus

#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1;
int n, m;
bool in_range(int i, int j){ return 0 < i && i <= n && 0 < j && j <= m; }
struct dsu{
		vector<int> rep, sz, on_stack, wrong;
		void init(int N){
				rep.resize(N+1), sz.resize(N+1), on_stack.resize(N+1, 0), wrong.resize(N+1, 0);
				for(int i = 1; i <= N; ++i) rep[i] = i, sz[i] = 1;
		}
		int Find(int x){
				if(x != rep[x]) rep[x] = Find(rep[x]);
				return rep[x];
		}
		void Union(int a, int b){ // nie muszę chyba przekazywać wrong w unionie, bo nigdy nie połączę ze złą spójną
				a = Find(a), b = Find(b);
				if(a == b) return;
				if(sz[a] < sz[b]) swap(a, b);
				rep[b] = a, sz[a] += sz[b], on_stack[a] += on_stack[b];
		}
};
void answer(){
		int k; scanf("%d%d%d", &k, &n, &m);
		char c = char(getchar_unlocked());
		unordered_map<char, int> mp; mp['N'] = 0, mp['E'] = 1, mp['S'] = 2, mp['W'] = 3;
		vector<int> h(k<<1);
		for(int i = 0; i < k; ++i) c = char(getchar_unlocked()), h[i] = mp[c], h[i+k] = mp[c];
		//~ for(int i = 0; i < k*2; ++i) printf("%d ", h[i]);
		//~ pn;
		vector<int> dp(16, 0); dp[0] = 0, dp[15] = inf;
		for(int msk = 1; msk < 15; ++msk){
				int len = 0;
				for(int i = 0; i < k*2; ++i){
						if(msk&(1<<h[i])) ++len;
						else dp[msk] = max(dp[msk], len), len = 0;
				}
				dp[msk] = max(dp[msk], len);
				if(dp[msk] == k*2) dp[msk] = inf;
				//~ printf("%d\n", dp[msk]);
		}
		
		vv<vv<int>> t(n+2, vv<int>(m+2, 0)), id(n+2, vv<int>(m+2, 0));
		vector<pii> pos(n*m+1);
		for(int i = 1; i <= n; ++i)
				for(int j = 1; j <= m; ++j) scanf("%d", &t[i][j]), id[i][j] = (i-1)*m+j, pos[(i-1)*m+j] = pii(i, j);
		
		dsu dsu; dsu.init(n*m);
		vector<int> st_dfs, st_rep, neigh(n*m+1, 0), vis(n*m+1, 0);
		vector<pii> dir(4); dir[0] = pii(-1, 0), dir[1] = pii(0, 1), dir[2] = pii(1, 0), dir[3] = pii(0, -1);
		
		for(int sty = 1; sty <= n; ++sty) for(int stx = 1; stx <= m; ++stx) if(t[sty][stx] && !vis[id[sty][stx]]){ // todo : pamietac, ze nie mozna wchodzic na te gdzie jest 0, sprawdzac, czy w on_stack jest find
				st_dfs.emplace_back(id[sty][stx]), st_rep.emplace_back(id[sty][stx]);
				dsu.on_stack[id[sty][stx]] = 1, vis[id[sty][stx]] = 1;
				
				while(!st_dfs.empty()){
						//~ for(int u : st_dfs) printf("%d ", u);
						//~ pn;
						//~ for(int u : st_rep) printf("%d ", u);
						//~ pn; pn;
						int x = st_dfs.back();
						if(neigh[x] > 3){
								st_dfs.pop_back(), --dsu.on_stack[dsu.Find(x)];
								if(!dsu.on_stack[dsu.Find(x)]) st_rep.pop_back();
								continue;
						}
						pii posx = pos[x], posu = pii(posx.fi+dir[neigh[x]].fi, posx.se+dir[neigh[x]].se);
						//~ printf("%d %d: %d\n", posx.fi, posx.se, dsu.Find(x));
						++neigh[x]; // todo: pamietac, by zwiekszac counter sasiada ++neigh[x]
						if(!t[posu.fi][posu.se] || !in_range(posu.fi, posu.se)) continue; 
						int u = id[posu.fi][posu.se];
						
						//~ tutaj chce wstawic jeszcze, czy da sie w ogole przejsc do goscia
						int msk = 0;
						for(int i = 0; i < 4; ++i)
								if(in_range(posu.fi+dir[i].fi, posu.se+dir[i].se) && dsu.Find(id[posu.fi+dir[i].fi][posu.se+dir[i].se]) == dsu.Find(x)) msk |= 1<<i;
						if(dp[msk] < t[posu.fi][posu.se]) continue;
						
						if(!vis[u]){
								st_dfs.emplace_back(u), st_rep.emplace_back(u);
								dsu.on_stack[u] = 1, vis[u] = 1;
						}
						else if(dsu.on_stack[dsu.Find(u)]){
								int sp = dsu.Find(u); // tutaj jakis assercik czy nie jest pusty, ale nie powinien
								while(st_rep.back() != sp) dsu.Union(st_rep.back(), sp), st_rep.pop_back();
								st_rep.pop_back(), st_rep.emplace_back(dsu.Find(u));
						}
						else{
								int sp = dsu.Find(x); dsu.wrong[sp] = 1;
								while(!st_dfs.empty() && dsu.Find(st_dfs.back()) == sp) st_dfs.pop_back();
								st_rep.pop_back(), dsu.on_stack[sp] = 0;
						}
				}
		}
		
		for(int i = 1; i <= n; ++i)
				for(int j = 1; j <= m; ++j) if(!t[i][j]) dsu.wrong[id[i][j]] = 1;
		int result = inf, cnt = 0;
		for(int i = 1, a; i <= n*m; ++i){
				a = dsu.Find(i);
				//~ printf("%d: %d\n", i, a);
				if(!dsu.wrong[a]){
						if(dsu.sz[a] < result) result = dsu.sz[a], cnt = 1;
						else if(dsu.sz[a] == result) ++cnt;
				}
				dsu.wrong[a] = 1;
		}
		printf("%d\n%d\n", result, result*cnt);
}
int main(){
		int T = 1;
		for(++T; --T; ) answer();
		return 0;
}

Compilation message (stderr)

virus.cpp: In function 'void answer()':
virus.cpp:33:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   int k; scanf("%d%d%d", &k, &n, &m);
      |          ~~~~~^~~~~~~~~~~~~~~~~~~~~~
virus.cpp:55:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     for(int j = 1; j <= m; ++j) scanf("%d", &t[i][j]), id[i][j] = (i-1)*m+j, pos[(i-1)*m+j] = pii(i, j);
      |                                 ~~~~~^~~~~~~~~~~~~~~~

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