Submission #239079

#	Time	Username	Problem	Language	Result	Execution time	Memory
239079		urd05	무지개나라 (APIO17_rainbow)	C++14	11 / 100	71 ms	4364 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[51][51];
    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[x][y]=find(p[x][y].first,p[x][y].second);
        return p[x][y];
    }
    int merge(P a,P b) {
        a=find(a.first,a.second);
        b=find(b.first,b.second);
        if (a==b) {
            return 0;
        }
        p[b.first][b.second]=a;
        return 1;
    }
};

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&&arr[x][y]==0) {
                        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) {
        return solve1(ar,ac,br,bc);
    }
}

Compilation message (stderr)

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:98:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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