Submission #677722

#	Time	Username	Problem	Language	Result	Execution time	Memory
677722		Cross_Ratio	Virus Experiment (JOI19_virus)	C++14	6 / 100	2081 ms	11064 KiB

virus

#include <bits/stdc++.h>
using namespace std;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int A[100005];
int B[200005];
int res[805][805];
bool vis[805][805];
int T[805][805];
int N, R, C;
int val[16];
bool in(int x, int y) {
    return 0<=x&&x<R&&0<=y&&y<C;
}
int D[805][805];
typedef pair<int,int> P;
bool pos[805][805][4];
int dir_map[3][3] = {
    { -1,3,-1 },
    { 2,-1,0  },
    { -1,1,-1 }
};
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> R >> C;
    string s;
    cin >> s;
    int i, j;
    for(i=0;i<N;i++) {
        for(j=0;j<4;j++) {
            if(s[i]=="WNES"[j]) A[i] = j;
        }
    }
    for(j=0;j<16;j++) {
        for(i=0;i<N;i++) B[i] = 0;
        bool VS[4] = {0, 0, 0, 0};
        for(int k = 0; k < 4; k++) {
            if(j&(1<<k)) VS[k] = true;
        }
        for(i=0;i<N;i++) {
            if(VS[A[i]]) B[i] = 1;
        }
        for(i=N;i<2*N;i++) B[i] = B[i-N];
        for(i=1;i<2*N;i++) {
            if(B[i]!=0) B[i] = B[i-1] + 1;
        }
        for(i=0;i<2*N;i++) val[j] = max(val[j], B[i]);
        if(val[j] >= N) val[j] = 100001;
    }
    for(i=0;i<R;i++) {
        for(j=0;j<C;j++) cin >> D[i][j];
    }
    for(i=0;i<R;i++) {
        for(j=0;j<C;j++) {
            T[i][j] = 0;
        }
    }
    for(i=0;i<R;i++) {
        for(j=0;j<C;j++) {
            if(D[i][j]==0) continue;
            //cout << i << ' ' << j << "'s Turn\n";
            vis[i][j] = true;
            res[i][j] = 1;
            queue<P> Q;
            vector<array<int, 2>> F;
            F.push_back({i, j});
            for(int dir = 0; dir < 4; dir++) {
                int x1 = i + dx[dir], y1 = j + dy[dir];
                if(in(x1, y1)) {
                    if(T[x1][y1]==0) F.push_back({x1, y1});
                    T[x1][y1] += (1<<dir);
                    if(D[x1][y1]!=0&&val[T[x1][y1]]>=D[x1][y1]) Q.push(P(x1, y1));
                }
            }
            while(!Q.empty()) {
                P k = Q.front();
                Q.pop();
                int x = k.first, y = k.second;
                //cout << x << ' ' << y <<'\n';
                if(vis[x][y]) continue;
                vis[x][y] = true;
                if(abs(x-i)+abs(y-j)<=1) {
                    int num = dir_map[x-i+1][y-j+1];
                    pos[i][j][num] = true;
                    if(pos[x][y][(num+2)%4]) {
                        res[i][j] = res[x][y];
                        break;
                    }
                }
                res[i][j]++;
                for(int k2 = 0; k2 < 4; k2++) {
                    int x1 = x + dx[k2], y1 = y + dy[k2];
                    if(in(x1, y1)) {
                        if(vis[x1][y1]) continue;
                        if(val[T[x1][y1]]>=D[x1][y1]) continue;
                        if(T[x1][y1]==0) F.push_back({x1, y1});
                        T[x1][y1] += (1<<k2);
                        if(D[x1][y1]!=0&&val[T[x1][y1]]>=D[x1][y1]) Q.push(P(x1, y1));
                    }
                }
            }
            for(auto k : F) T[k[0]][k[1]] = 0;
            for(auto k : F) vis[k[0]][k[1]] = false;
        }
    }
    int mi = R*C+1, micnt = 0;
    for(i=0;i<R;i++) {
        for(j=0;j<C;j++) {
            if(D[i][j]==0) continue;
            if(res[i][j] < mi) {
                mi = res[i][j];
                micnt = 0;
            }
            if(res[i][j]==mi) micnt++;
        }
    }
    /*for(i=0;i<R;i++) {
        for(j=0;j<C;j++) cout << res[i][j] << ' ';
        cout << '\n';
    }*/
    cout << mi << '\n' << micnt;
}

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