Submission #1262675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262675		user736482	Tourism (JOI23_tourism)	C++20	0 / 100	5 ms	8260 KiB

tourism

    #pragma GCC optimize("O3")
    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define ld long double
    #define pb push_back
    #define ff first
    #define ss second
    #define MOD 1000000007
    #define INF 1000000019
    #define POT (1<<20)
    #define INFL 1000000000000000099

    ll r,c,cnt;
    ll odw[407][407][2];
    vector<pair<pair<ll,ll>,ll>>g[407][407][2];
    void dfs(ll x,ll y,ll z){
        if(cnt>r*c)return;
        //cout<<"   "<<odw[x][y][z]<<" "<<x<<" "<<y<<"\n";
        if(odw[x][y][z]==1)cnt=INFL;
        if(odw[x][y][z])return;
        odw[x][y][z]=1;
        cnt++;
        for(auto i : g[x][y][z])dfs(i.ff.ff,i.ff.ss,i.ss);
        odw[x][y][z]=2;
    }
    vector<vector<ll>>pol(vector<vector<char>>v){
        //cout<<"xd"<<flush;
        //return {};
        for(ll i=0;i<r+7;i++)for(ll j=0;j<c+7;j++)for(ll m=0;m<2;m++)g[i][j][m].clear();
        for(ll i=0;i<r;i++){
            for(ll j=0;j<c;j++){
                for(ll k=0;k<2;k++){
                    vector<pair<pair<ll,ll>,ll>>pom;
                    if(k==0 && v[i][j]=='Z'){
                        if(i)
                        pom.pb({{i-1,j},0});
                        if(j)
                        pom.pb({{i,j-1},v[i][j-1]=='N'});
                    }
                    if(k==1 && v[i][j]=='N'){
                        if(i<r-1)
                        pom.pb({{i+1,j},1});
                        if(j)
                        pom.pb({{i,j-1},v[i][j-1]=='N'});
                    }
                    if(k==1 && v[i][j]=='Z'){
                        if(i<r-1)
                        pom.pb({{i+1,j},1});
                        if(j<c-1)
                        pom.pb({{i,j+1},v[i][j+1]!='N'});
                    }
                    if(k==0 && v[i][j]=='N'){

                        if(i)
                        pom.pb({{i-1,j},0});
                        if(j<c-1)
                        pom.pb({{i,j+1},v[i][j+1]!='N'});
                    }
                // cout<<i<<" "<<j<<" "<<k<<"\n\n";
                    for(auto m : pom){
                    //   cout<<m.ff.ff<<" "<<m.ff.ss<<" "<<m.ss<<"\n";
                    
                    g[i][j][k].pb(m);
                    }
                    
                    //cout<<"\n\n"<<flush;
                }
            }
        }
        vector<vector<ll>>ans(r);
        for(ll i=0;i<c;i++){
            cnt=0;
            for(ll j=0;j<r+7;j++){
                for(ll k=0;k<c+7;k++)for(ll m=0;m<2;m++)odw[j][k][m]=0;
            }
            //cout<<i<<": "<<flush;
            //cout<<r<<" "<<c<<"    "<<flush;
            for(ll j=0;j<r;j++){
                dfs(j,i,0);
                //cout<<"xd"<<flush;
                ans[j].pb(cnt);
            // cout<<cnt<<" ";
            }
            //cout<<"\n\n";
            cnt=0;
            for(ll j=0;j<r+7;j++){
                for(ll k=0;k<c+7;k++)for(ll m=0;m<2;m++)odw[j][k][m]=0;
            }
            for(ll j=r-1;j>=0;j--){
                dfs(j,i,1);
                ans[j][i]=min(ans[j][i],cnt);
            }
        }
        return ans;
    }
    vector<vector<char>>v;
    int main(){
        
        cin>>r>>c;
        
        //return 0;

        for(ll i=0;i<r;i++){v.pb({});for(ll j=0;j<c;j++){v[i].pb(0);cin>>v[i][j];}}
        //cout<<"xd"<<flush;
        vector<vector<ll>>a=pol(v);
        //return 0;
        for(auto i : a){for(ll j : i)if(j<=r*c)cout<<j*2<<" ";else cout<<-1<<" ";cout<<"\n";}
    }

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41