Submission #1042953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042953		phong	Virus Experiment (JOI19_virus)	C++17	0 / 100	136 ms	262144 KiB

virus

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
const int nmax = 800 + 5, N = 1e5;
const ll oo = 1e9;
const int lg = 31, M = 2, mod = 1e6;
#define pii pair<ll, ll>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
#define endl "\n"
#define task "code"
using namespace std;

int n, m, sz;
string s;
queue<pii> q;
int vis[nmax][nmax], r[nmax * nmax];
ll F[1 << 4];
int pos[nmax][4], a[nmax][nmax];

int gg(char x){
    if(x == 'N') return 0;
    if(x == 'E') return 1;
    if(x == 'S') return 2;
    return 3;
}

int bit(int msk, int x){
    return msk >> x & 1;
}

int get(int u){
    return r[u] ? r[u] = get(r[u]) : u;
}

int calc(int i, int j){
    return (i - 1) * m + j;
}

bool okok[nmax * nmax];

void Union(int u, int v){
    if(okok[v]){
        okok[u] = 1;
        return;
    }
    r[u] = v;
}

int scc = 0;
queue<pii> one;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int ans[nmax][nmax];

vector<pii> two;

void bfs(int x, int y){
    while(one.size()) one.pop();
    two.clear();
    one.push({x, y});
    ++scc;
    vis[x][y] = scc;
    while(one.size()){
        pii tmp = one.front();one.pop();
        int i = tmp.fi;
        int j = tmp.se;
        two.push_back({i, j});
        for(int k = 0;k < 4; ++k){
            int new_i = dx[k] + i;
            int new_j = dy[k] + j;
            if(new_i >= 1 && new_i <= n && new_j >= 1 && new_j <= m && vis[new_i][new_j] != scc && a[new_i][new_j]){
                int w = 0;

                for(int z = 0; z < 4; ++z){
                    int u = new_i + dx[z];
                    int v = new_j + dy[z];
                    if(vis[u][v] == scc) w |= (1 << z);
                }
                if(F[w] >= a[new_i][new_j]){
                    int c1 = calc(i, j);
                    int c2 = calc(new_i, new_j);
                    c1 = get(c1), c2 = get(c2);
                    if(c1 != c2){
                        Union(c1, c2);
                        return;
                    }
                    vis[new_i][new_j] = scc;
                    one.push({new_i, new_j});
                }
            }
        }
    }
//    for(auto [i, j] : two) cout << i << ' ' << j << endl;
//    cout << "#####";
    for(auto [i, j] : two) ans[i][j] = two.size();
    okok[get(calc(x, y))] = 1;

}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen(task".inp", "r", stdin);
//    freopen(task".out", "w", stdout);
    cin >> sz >> n >> m;
    cin >> s;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> a[i][j];
        }
    }
    s = s + s;
    sz *= 2;
    s = ' ' + s;
    for(int j = 0; j < 4; ++j) pos[sz + 1][j] = pos[sz + 2][j] = sz + 1;
    for(int i = sz; i >= 1; --i){
        for(int j = 0; j < 4; ++j) pos[i][j] = pos[i + 1][j];
        pos[i][gg(s[i])] = i;
    }
    for(int i = 1; i <= sz; ++i){
        for(int msk = 1; msk < (1 << 4); ++msk){
            int mi = sz + 1;
            for(int j = 0; j < 4; ++j){
                if(!bit(msk, j)) mi = min(mi, pos[i][j]);
            }
            F[msk] = max(F[msk], (ll)mi - i);
        }
    }
    for(int msk = 0; msk < (1 << 4) ;++msk) if(F[msk] == sz) F[msk] = oo;
    memset(ans, 0x3f, sizeof ans);
    //boruvka

    while(1){
        bool ok = 0;
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= m; ++j){
                if(!a[i][j] || get(calc(i, j)) != calc(i, j) || okok[get(calc(i, j))]) continue;
                bfs(i, j);
                ok = 1;

            }
        }
        if(!ok) break;
    }
    int mi = oo, cnt = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
//            cout << ans[i][j] << ' ';
            if(mi > ans[i][j]){
                cnt = 0;
                mi = ans[i][j];
            }
            if(mi == ans[i][j]) cnt++;
        }
//        cout << endl;
    }
    cout <<mi << '\n' << cnt << endl;

}
/*
6 3 4
SWNEES
2 1 1 2
1 0 1 3
1 1 2 2
0 1 2 3 2 2 4 5 1 2 2 4 3 4 5 1000000000
*/

Compilation message (stderr)

virus.cpp:104:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  104 | main(){
      | ^~~~

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