oj.uz

Submission #229666

# Submission time Handle Problem Language Result Execution time Memory
229666 2020-05-05T19:18:15 Z thebes Virus Experiment (JOI19_virus) C++14
14 / 100
 402 ms 101856 KB 
#include <bits/stdc++.h>
#define DEBUG 1
using namespace std;

namespace output{
    void __(short x){cout<<x;}
    void __(unsigned x){cout<<x;}
    void __(int x){cout<<x;}
    void __(long long x){cout<<x;}
    void __(unsigned long long x){cout<<x;}
    void __(double x){cout<<x;}
    void __(long double x){cout<<x;}
    void __(char x){cout<<x;}
    void __(const char*x){cout<<x;}
    void __(const string&x){cout<<x;}
    void __(bool x){cout<<(x?"true":"false");}
    template<class S,class T>
    void __(const pair<S,T>&x){__(DEBUG?"(":""),__(x.first),__(DEBUG?", ":" "),__(x.second),__(DEBUG?")":"");}
    template<class T>
    void __(const vector<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class T>
    void __(const set<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class T>
    void __(const multiset<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class S,class T>
    void __(const map<S,T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    void pr(){cout<<"\n";}
    template<class S,class... T>
    void pr(const S&a,const T&...b){__(a);if(sizeof...(b))__(' ');pr(b...);}
}

using namespace output;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,char> pic;
typedef pair<double,double> pdd;
typedef pair<ld,ld> pld;
typedef vector<int> vi;
typedef vector<ll> vl;

#define pb push_back
#define fox(i,x,y) for(int i=(x);i<=(y);i++)
#define foxr(i,x,y) for(int i=(y);i>=(x);i--)
#define F first
#define S second

const int MN = 808, MM = 1e5+5;
int N, M, K, i, j, k, x, y, a[MN][MN], dx[]={-1,1,0,0}, dy[]={0,0,-1,1}, ds[MN*MN], vs[MN*MN], len[1<<4], sz[MN*MN], ans, cnt;
string s; char op[]={'N','S','W','E'}; set<char> ok;
queue<pii> q; vector<pii> *elem[MN*MN], *go[MN*MN];
stack<int> stk; bitset<MN*MN> st; int dep[MN*MN];

inline int id(int x,int y){return (x-1)*M+y;}
int fnd(int x){return ds[x]=x==ds[x]?x:fnd(ds[x]);}
inline bool flood(int x,int y,int cc){
    if(a[x][y]==0) return 0;
    int msk = 0;
    for(int i=0;i<4;i++){
        int nx=x+dx[i], ny=y+dy[i];
        if(nx<1||nx>N||ny<1||ny>M) continue;
        if(fnd(id(nx,ny))==cc) msk |= (1<<i);
    }
    return len[msk]>=a[x][y];
}

void augment(int cc){
    vs[cc] = 1;
    while(go[cc]->size()){
        pii v=go[cc]->back();
        go[cc]->pop_back();
        elem[cc]->pb(v);
        for(int i=0;i<4;i++){
            int nx=v.F+dx[i], ny=v.S+dy[i];
            if(nx<1||nx>N||ny<1||ny>M) continue;
            if(fnd(id(nx,ny))!=cc&&flood(nx,ny,cc)){
                if(st[fnd(id(nx,ny))]){
                    int anc = fnd(id(nx,ny));
                    while(stk.size()){
                        int x=stk.top(); stk.pop();
                        ds[x]=cc; st[x]=0;
                        if(elem[x]->size()>elem[cc]->size())
                            swap(elem[x],elem[cc]);
                        for(auto v : *elem[x])
                            go[cc]->pb(v);
                        elem[x]->clear();
                        if(x==anc) break;;
                    }
                }
                else if(!vs[fnd(id(nx,ny))]){
                    cc = fnd(cc);
                    stk.push(cc), st[cc]=1;
                    augment(fnd(id(nx,ny)));
                    if(stk.size()&&stk.top()==cc) stk.pop();
                    st[cc]=0;
                    cc = fnd(cc);
                }
            }
        }
    }
}

int main(){
    cin >> K >> N >> M >> s;
    for(i=0;i<(1<<4);i++){
        int cur = 0;
        ok.clear();
        for(j=0;j<4;j++)
            if((1<<j)&i) ok.insert(op[j]);
        for(k=0;k<=2*K;k++){
            if(ok.count(s[k%K])) cur++;
            else len[i]=max(len[i],cur), cur=0;
        }
        len[i]=max(len[i],cur);
        if(len[i]>=2*K) len[i]=111111;
        //pr(">>>",i,len[i]);
    }
    for(i=1;i<=N;i++){
        for(j=1;j<=M;j++){
            scanf("%d",&a[i][j]);
            ds[id(i,j)]=id(i,j);
            go[id(i,j)]=new vector<pii>();
            elem[id(i,j)]=new vector<pii>();
            go[id(i,j)]->pb({i,j});
        }
    }
    for(i=1;i<=N;i++){
        for(j=1;j<=M;j++){
            if(!vs[fnd(id(i,j))]&&a[i][j]) augment(id(i,j));
        }
    }
    ans = 1<<30;
    memset(vs,0,sizeof(vs));
    for(i=1;i<=N;i++){
        for(j=1;j<=M;j++)
            sz[fnd(id(i,j))]++;
    }
    for(i=1;i<=N;i++){
        for(j=1;j<=N;j++){
            if(!a[i][j]) continue;
            int cur_id = fnd(id(i,j));
            if(!vs[cur_id]){
                vs[cur_id] = 1;
                //pr(">",cur_id,sz[cur_id]);
                int aug = 0;
                for(auto v : *elem[cur_id]){
                    for(k=0;k<4;k++){
                        int nx=v.F+dx[k], ny=v.S+dy[k];
                        if(nx<1||nx>N||ny<1||ny>M) continue;
                        if(fnd(id(nx,ny))!=cur_id&&flood(nx,ny,cur_id))
                            aug = 1;
                    }
                }
                if(!aug){
                    if(sz[cur_id]<ans)
                        ans = cnt = sz[cur_id];
                    else if(sz[cur_id]==ans)
                        cnt += sz[cur_id];
                }
            }
        }
    }
    printf("%d\n%d\n",ans,cnt);
    return 0;
}

Compilation message

virus.cpp: In function 'int main()':
virus.cpp:122:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a[i][j]);
             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3072 KB Output is correct
2 Correct 392 ms 100832 KB Output is correct
3 Correct 402 ms 100908 KB Output is correct
4 Correct 369 ms 100728 KB Output is correct
5 Correct 401 ms 100728 KB Output is correct
6 Correct 10 ms 5504 KB Output is correct
7 Correct 371 ms 101856 KB Output is correct
8 Correct 187 ms 42104 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2944 KB Output is correct
2 Correct 28 ms 3200 KB Output is correct
3 Correct 50 ms 3192 KB Output is correct
4 Correct 28 ms 3192 KB Output is correct
5 Correct 51 ms 3192 KB Output is correct
6 Correct 52 ms 3704 KB Output is correct
7 Correct 6 ms 2944 KB Output is correct
8 Correct 51 ms 3320 KB Output is correct
9 Correct 7 ms 3456 KB Output is correct
10 Correct 28 ms 3200 KB Output is correct
11 Correct 7 ms 3456 KB Output is correct
12 Incorrect 8 ms 3584 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3072 KB Output is correct
2 Correct 392 ms 100832 KB Output is correct
3 Correct 402 ms 100908 KB Output is correct
4 Correct 369 ms 100728 KB Output is correct
5 Correct 401 ms 100728 KB Output is correct
6 Correct 10 ms 5504 KB Output is correct
7 Correct 371 ms 101856 KB Output is correct
8 Correct 187 ms 42104 KB Output is correct
9 Correct 6 ms 2944 KB Output is correct
10 Correct 28 ms 3200 KB Output is correct
11 Correct 50 ms 3192 KB Output is correct
12 Correct 28 ms 3192 KB Output is correct
13 Correct 51 ms 3192 KB Output is correct
14 Correct 52 ms 3704 KB Output is correct
15 Correct 6 ms 2944 KB Output is correct
16 Correct 51 ms 3320 KB Output is correct
17 Correct 7 ms 3456 KB Output is correct
18 Correct 28 ms 3200 KB Output is correct
19 Correct 7 ms 3456 KB Output is correct
20 Incorrect 8 ms 3584 KB Output isn't correct
21 Halted 0 ms 0 KB -