제출 #915188

#제출 시각아이디문제언어결과실행 시간메모리
915188qin바이러스 (JOI19_virus)C++17
0 / 100
129 ms26892 KiB
#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; }

컴파일 시 표준 에러 (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);
      |                                 ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...