제출 #239082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
239082		urd05	무지개나라 (APIO17_rainbow)	C++14	11 / 100	85 ms	1680 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> st[3];
vector<int> en[3];
vector<int> ts;
vector<int> te;

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));
    }
    if (r==2) {
        for(int j=1;j<=2;j++) {
            bool flag=false;
            for(int i=1;i<=c;i++) {
                if (arr[j][i]==0) {
                    if (!flag) {
                        flag=true;
                        st[j].push_back(i);
                    }
                }
                if (arr[j][i]==1) {
                    if (flag) {
                        flag=false;
                        en[j].push_back(i-1);
                    }
                }
            }
            if (arr[j][c]==0) {
                en[j].push_back(c);
            }
        }
        bool flag=false;
        for(int i=1;i<=c;i++) {
            if (arr[1][i]==1&&arr[2][i]==1) {
                if (!flag) {
                    flag=true;
                    ts.push_back(i);
                }
            }
            else {
                if (flag) {
                    flag=false;
                    te.push_back(i-1);
                }
            }
        }
        if (arr[1][c]==1&&arr[2][c]==1) {
            te.push_back(c);
        }
    }
}

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 solve2(int ar,int ac,int br,int bc) {
    if (ar==br) {
        int fr=lower_bound(en[ar].begin(),en[ar].end(),ac)-en[ar].begin();
        int ba=upper_bound(st[ar].begin(),st[ar].end(),bc)-st[ar].begin()-1;
        int ret=ba-fr+1;
        return ret;
    }
    else {
        if (ac==bc) {
            return (arr[ar][ac]==1&&arr[ar][bc]==1)?0:1;
        }
        int fr=lower_bound(te.begin(),te.end(),ac)-te.begin();
        int ba=upper_bound(ts.begin(),ts.end(),bc)-ts.begin()-1;
        int ret=ba-fr;
        if (arr[1][ac]==0||arr[2][ac]==0) {
            ret++;
        }
        if (arr[2][bc]==0||arr[2][bc]==0) {
            ret++;
        }
        return ret;
    }
}

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

컴파일 시 표준 에러 (stderr) 메시지

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:168: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