Submission #775038

#	Time	Username	Problem	Language	Result	Execution time	Memory
775038		gagik_2007	Land of the Rainbow Gold (APIO17_rainbow)	C++17	11 / 100	3057 ms	1048576 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=5007;
ll n,m,k;
vector<vector<int>>a;
vector<vector<int>>used;

void init(int R, int C, int sr, int sc, int M, char* SSSSSS) {
    string S=SSSSSS;
    n=R;
    m=C;
    a.resize(n+2, vector<int>(0, 0));
    used.resize(n+2, vector<int>(0, 0));
    for(int i=0;i<=n+1;i++){
        a[i].resize(m+2, 0);
        used[i].resize(m+2, 0);
    }
    // cout<<"a: "<<a.size()<<"x"<<a[0].size()<<endl;
    // cout<<a[6][3]<<endl;
    int i=sr,j=sc;
    a[i][j]=1;
    for(int ch:S){
        if(ch=='N'){
            i--;
        }
        if(ch=='E'){
            j++;
        }
        if(ch=='S'){
            i++;
        }
        if(ch=='W'){
            j--;
        }
        a[i][j]=1;
    }
}

vector<pii>deltas={make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)};

void dfs(int i, int j, int mxi, int mni, int mxj, int mnj){
    // cout<<"DFS: "<<i<<" "<<j<<endl;
    used[i][j]=1;
    for(pii delta:deltas){
        int di=delta.ff;
        int dj=delta.ss;
        if(i+di<=mxi&&i+di>=mni&&j+dj<=mxj&&j+dj>=mnj){
            // cout<<"STUG: "<<i+di<<" "<<j+dj<<endl;
            if(!used[i+di][j+dj]&&!a[i+di][j+dj]){
                // cout<<"STUG OK"<<endl;
                dfs(i+di,j+dj,mxi,mni,mxj,mnj);
            }
            // cout<<"STUG EXAV"<<endl;
        }
    }
}

int colour(int ar, int ac, int br, int bc) {
    // cout<<"QUERY: "<<ar<<" "<<ac<<" "<<br<<" "<<bc<<endl;
    int cnt=0;
    for(int i=ar;i<=br;i++){
        for(int j=ac;j<=bc;j++){
            if(!used[i][j]&&!a[i][j]){
                cnt++;
                dfs(i,j,br,ar,bc,ac);
            }
        }
    }
    for(int i=ar;i<=br;i++){
        for(int j=ac;j<=bc;j++){
            used[i][j]=0;
        }
    }
    return cnt;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26