Submission #258900

#	Time	Username	Problem	Language	Result	Execution time	Memory
258900		Mercenary	Virus Experiment (JOI19_virus)	C++14	100 / 100	379 ms	12280 KiB

virus

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 800 + 5;
const int logn = log2(maxn) + 1;
int lab[maxn * maxn];
bool ok[maxn][maxn];
int a[maxn][maxn];
int best[16];
int vis[maxn][maxn];

int n , m , k;
string s;
int dx[] = {-1 , 1 , 0 , 0};
int dy[] = {0 , 0 , -1 ,1};

int to2d(int x , int y){
    return x * n + y;
}

bool valid(int x , int y){
    if(x < 0 || y < 0 || x >= m || y >= n)return 0;
    return a[x][y] > 0;
}

int FindLab(int u){
    return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }

    {
        cin >> k >> m >> n >> s;
        for(auto & c : s){
            if(c == 'N')c = 0;
            else if(c == 'S')c = 1;
            else if(c == 'W')c = 2;
            else c = 3;
        }
        for(int i = 0 ; i < m ; ++i)for(int j = 0 ; j < n ; ++j)cin >> a[i][j];
    }

    {
        for(int msk = 0 ; msk < 16 ; ++msk){
            int j = -1;
            for(int i = 0 ; i < 2 * k ; ++i){
                if(msk & (1 << s[i % k]))best[msk] = max(best[msk] , i - j);
                else j = i;
            }
            if(best[msk] >= k)best[msk] = 1e9;
        }
    }

    {
        int nTime = 0;
        memset(lab,-1,sizeof lab);
        bool flag = 0;
        ii res = mp(1e9,0);
        do{
            flag = 0;
            for(int i = 0 ; i < m ; ++i){
                for(int j = 0 ; j < n ; ++j){
                    if(a[i][j] > 0 && ok[i][j] == 0 && lab[to2d(i , j)] < 0){
                        flag = 1;
                        queue<ii> q;q.push(mp(i,j));
                        vis[i][j] = ++nTime;
                        ii other = mp(-1 , -1);
                        int sum = 0;
                        while(q.size()){
                            auto u = q.front();q.pop();sum++;
                            for(int t = 0 ; t < 4 ; ++t){
                                int x = u.first + dx[t] , y = u.second + dy[t];
                                if(!valid(x , y) || vis[x][y] == nTime)continue;
                                int msk = 0;
                                for(int tt = 0 ; tt < 4 ; ++tt){
                                    if(valid(x + dx[tt] , y + dy[tt]) && vis[x + dx[tt]][y + dy[tt]] == nTime){
                                        msk |= (1 << tt);
                                    }
                                }
                                if(best[msk] >= a[x][y]){
                                    if(FindLab(to2d(x,y)) != to2d(i,j)){
                                        other = mp(x,y);
                                    }else{
                                        q.push(mp(x,y));
                                        vis[x][y] = nTime;
                                    }
                                }
                            }
                            if(other != mp(-1,-1))break;
                        }
                        ok[i][j] = 1;
                        if(other == mp(-1,-1)){
                            if(res.first > sum)res = mp(sum,sum);
                            else if(res.first == sum)res.second += sum;
                        }else {
                            int tmp = FindLab(to2d(other.first,other.second));
                            if(ok[tmp / n][tmp % n] == 0){
                                lab[tmp] += lab[to2d(i,j)];
                                lab[to2d(i,j)] = tmp;
                            }
                        }
                    }
                }
            }
        }while(flag);
        cout << res.first << " " << res.second << endl;
    }
}

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:48:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
virus.cpp:49:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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