oj.uz

Submission #229647

# Submission time Handle Problem Language Result Execution time Memory
229647 2020-05-05T15:45:50 Z thebes Virus Experiment (JOI19_virus) C++14
14 / 100
 502 ms 61176 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], ans, cnt;
string s; char op[]={'N','S','W','E'}; set<char> ok;
queue<pii> q; vector<pii> *elem[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];
}
inline bool con(int x,int y,int cc){
    if(a[x][y]==0) return 0;
    int msk = 0, ok = 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);
        if(fnd(id(nx,ny))==cc&&flood(nx,ny,fnd(id(x,y)))) ok = 1;
    }
    return len[msk]>=a[x][y]&&ok;
}

void augment(int old,int cc){
    // augment
    vs[old] = 1;
    set<int> nxt;
    for(auto cell : *elem[old]){
        for(int i=0;i<4;i++){
            int nx=cell.F+dx[i], ny=cell.S+dy[i];
            if(nx<1||nx>N||ny<1||ny>M) continue;
            if(fnd(id(nx,ny))==cc||nxt.count(fnd(id(nx,ny)))) continue;
            if(con(nx,ny,cc)) nxt.insert(fnd(id(nx,ny)));
        }
    }
    if(old!=cc){ // need to merge
        if(elem[old]->size()>elem[cc]->size()) swap(elem[old],elem[cc]);
        for(auto v : *elem[old])
            elem[cc]->pb(v);
        elem[old]->clear();
    }
    for(auto v : nxt)
        ds[v] = cc;
    for(auto v : nxt)
        augment(v, 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<=100111;k++){
            if(ok.count(s[k%K])) cur++;
            else len[i]=max(len[i],cur), cur=0;
        }
        len[i]=max(len[i],cur);
    }
    for(i=1;i<=N;i++){
        for(j=1;j<=M;j++){
            scanf("%d",&a[i][j]);
            ds[id(i,j)]=id(i,j);
            elem[id(i,j)]=new vector<pii>();
            elem[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),id(i,j));
        }
    }
    ans = 1<<30;
    memset(vs,0,sizeof(vs));
    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;
                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(elem[cur_id]->size()<ans)
                        ans = cnt = elem[cur_id]->size();
                    else if(elem[cur_id]->size()==ans)
                        cnt += elem[cur_id]->size();
                }
            }
        }
    }
    printf("%d\n%d\n",ans,cnt);
    return 0;
}

Compilation message

virus.cpp: In function 'int main()':
virus.cpp:147:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if(elem[cur_id]->size()<ans)
                        ~~~~~~~~~~~~~~~~~~~~^~~~
virus.cpp:149:49: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     else if(elem[cur_id]->size()==ans)
                             ~~~~~~~~~~~~~~~~~~~~^~~~~
virus.cpp:118: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 17 ms 3072 KB Output is correct
2 Correct 447 ms 54652 KB Output is correct
3 Correct 447 ms 56568 KB Output is correct
4 Correct 436 ms 54264 KB Output is correct
5 Correct 457 ms 56696 KB Output is correct
6 Correct 22 ms 5504 KB Output is correct
7 Correct 502 ms 61176 KB Output is correct
8 Correct 181 ms 24568 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2944 KB Output is correct
2 Correct 19 ms 3200 KB Output is correct
3 Correct 32 ms 3320 KB Output is correct
4 Correct 19 ms 3200 KB Output is correct
5 Correct 31 ms 3192 KB Output is correct
6 Correct 33 ms 3832 KB Output is correct
7 Correct 18 ms 2944 KB Output is correct
8 Correct 31 ms 3388 KB Output is correct
9 Correct 20 ms 3200 KB Output is correct
10 Correct 19 ms 3320 KB Output is correct
11 Correct 20 ms 3200 KB Output is correct
12 Incorrect 21 ms 3456 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3072 KB Output is correct
2 Correct 447 ms 54652 KB Output is correct
3 Correct 447 ms 56568 KB Output is correct
4 Correct 436 ms 54264 KB Output is correct
5 Correct 457 ms 56696 KB Output is correct
6 Correct 22 ms 5504 KB Output is correct
7 Correct 502 ms 61176 KB Output is correct
8 Correct 181 ms 24568 KB Output is correct
9 Correct 18 ms 2944 KB Output is correct
10 Correct 19 ms 3200 KB Output is correct
11 Correct 32 ms 3320 KB Output is correct
12 Correct 19 ms 3200 KB Output is correct
13 Correct 31 ms 3192 KB Output is correct
14 Correct 33 ms 3832 KB Output is correct
15 Correct 18 ms 2944 KB Output is correct
16 Correct 31 ms 3388 KB Output is correct
17 Correct 20 ms 3200 KB Output is correct
18 Correct 19 ms 3320 KB Output is correct
19 Correct 20 ms 3200 KB Output is correct
20 Incorrect 21 ms 3456 KB Output isn't correct
21 Halted 0 ms 0 KB -