Submission #239075

#	Time	Username	Problem	Language	Result	Execution time	Memory
239075		urd05	Land of the Rainbow Gold (APIO17_rainbow)	C++14	0 / 100	8 ms	1024 KiB

rainbow

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

char str[100001];
int r,c,sr,sc;
int l;
int arr[51][200001];
typedef pair<int,int> P;
vector<int> check[3];

void init(int rr,int cc,int srr,int scc,int m,char s[]) {
    r=rr;
    c=cc;
    sr=srr;
    sc=scc;
    l=m;
    for(int i=0;i<m;i++) {
        str[i]=s[i];
    }
    arr[sr][sc]=1;
    vector<P> v;
    int x=sr;
    int y=sc;
    v.push_back(P(x,y));
    for(int i=0;i<m;i++) {
        if (str[i]=='W') {
            y--;
        }
        if (str[i]=='E') {
            y++;
        }
        if (str[i]=='N') {
            x--;
        }
        if (str[i]=='S') {
            x++;
        }
        arr[x][y]=1;
        v.push_back(P(x,y));
    }
}

struct UnionFind {
    P p[50][50];
    void init() {
        for(int i=1;i<=r;i++) {
            for(int j=1;j<=c;j++) {
                p[i][j]=P(-1,-1);
            }
        }
    }
    P find(int x,int y) {
        if (p[x][y]<P(0,0)) {
            return P(x,y);
        }
        P got=find(p[x][y].first,p[x][y].second);
        p[x][y]=got;
        return got;
    }
    bool merge(P a,P b) {
        a=find(a.first,a.second);
        b=find(b.first,b.second);
        if (a==b) {
            return false;
        }
        p[b.first][b.second]=a;
        return true;
    }
};

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int solve1(int ar,int ac,int br,int bc) {
    UnionFind uf;
    uf.init();
    int sum=0;
    for(int i=ar;i<=br;i++) {
        for(int j=ac;j<=bc;j++) {
            if (arr[i][j]==0) {
                sum++;
                for(int k=0;k<4;k++) {
                    int x=i+dx[k];
                    int y=j+dy[k];
                    if (x>=ar&&x<=br&&y>=ac&&y<=bc) {
                        sum-=uf.merge(P(i,j),P(x,y));
                    }
                }
            }
        }
    }
    return sum;
}

int colour(int ar,int ac,int br,int bc) {
    if (r<=50&&c<=50) {
        solve1(ar,ac,br,bc);
    }
}

Compilation message (stderr)

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:99:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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