제출 #624333

#제출 시각아이디문제언어결과실행 시간메모리
624333urosk바이러스 (JOI19_virus)C++14
0 / 100
2 ms2900 KiB
#define here cerr<<"===========================================\n" #define dbg(x) cerr<<#x<<": "<<x<<endl; #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> #define ld double #define ll long long #define llinf 100000000000000000LL // 10^17 #define pb push_back #define popb pop_back #define fi first #define sc second #define endl '\n' #define pll pair<ll,ll> #define pld pair<ld,ld> #define sz(a) (ll)(a.size()) #define all(a) a.begin(),a.end() #define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;} #define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0); using namespace std; using namespace __gnu_pbds; /* ll add(ll x,ll y){ x+=y; if(x<0){ x%=mod; x+=mod; }else{ if(x>=mod) x%=mod; } return x; } ll mul(ll a,ll b){ ll ans = (a*b)%mod; if(ans<0) ans+=mod; return ans; } */ typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll rnd(ll l,ll r){ return uniform_int_distribution<ll>(l,r)(rng); } #define maxn 100005 #define maxc 805 ll d,n,m; ll cnt[5]; ll a[maxc][maxc]; ll id[maxc][maxc]; ll tsz = 0; vector<ll> g[maxn]; vector<ll> dx = {-1,1,0,0}; vector<ll> dy = {0,0,-1,1}; bool valid(ll x,ll y){return x>=1&&x<=n&&y>=1&&y<=m;} ll low[maxn],vis[maxn],in[maxn],comp[maxn],deg[maxn],cdeg[maxn],siz[maxn]; bool na[maxn]; ll timer = 0; ll csz = 0; stack<ll> s; void dfs(ll u){ vis[u] = 1; na[u] = 1; s.push(u); in[u] = ++timer; low[u] = in[u]; for(ll s : g[u]){ if(!vis[s]) dfs(s); if(na[s]) low[u] = min(low[u],low[s]); } if(low[u]==in[u]){ ++csz; while(sz(s)){ ll v = s.top(); comp[v] = csz; na[v] = 0; s.pop(); siz[csz]++; if(v==u) break; } } } int main(){ daj_mi_malo_vremena cin >> d >> n >> m; string s; cin >> s; for(char c : s){ if(c=='S') cnt[1]++; if(c=='N') cnt[0]++; if(c=='E') cnt[3]++; if(c=='W') cnt[2]++; } for(ll i = 1;i<=n;i++) for(ll j = 1;j<=m;j++){cin >> a[i][j];if(a[i][j]==0) a[i][j] = llinf;id[i][j]=++tsz;} for(ll i = 1;i<=n;i++){ for(ll j = 1;j<=m;j++){ if(a[i][j]==llinf) continue; for(ll e = 0;e<4;e++){ ll ni = i + dx[e],nj = j + dy[e]; if(!valid(ni,nj)||(cnt[e]<a[ni][nj])) continue; ll x = id[i][j],y = id[ni][nj]; g[x].pb(y); deg[y]++; } } } for(ll i = 1;i<=tsz;i++) if(!deg[i]) dfs(i); for(ll i = 1;i<=tsz;i++){ for(ll j : g[i]) cdeg[comp[j]]++; } ll ans = 0,cnt = 0; for(ll i = 1;i<=csz;i++){ if(siz[i]>ans) ans = siz[i],cnt = siz[i]; else if(siz[i]==ans) cnt+=siz[i]; } cout<<ans<<endl; cout<<cnt<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...