제출 #59359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59359		duality	무지개나라 (APIO17_rainbow)	C++11	12 / 100	157 ms	28588 KiB

rainbow

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long int LLI;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
#include "rainbow.h"

int r,c;
vpii p;
int grid[2][200000];
vi num[200000];
vpii r1,r2,r12;
void init(int R,int C,int sr,int sc,int M,char *S) {
    int i;
    r = R,c = C;
    sr--,sc--;
    p.pb(mp(sr,sc));
    for (i = 0; i < M; i++) {
        if (S[i] == 'N') sr--;
        else if (S[i] == 'S') sr++;
        else if (S[i] == 'W') sc--;
        else sc++;
        p.pb(mp(sr,sc));
    }
    sort(p.begin(),p.end());
    p.resize(unique(p.begin(),p.end())-p.begin());
    if (R == 2) {
        for (i = 0; i < p.size(); i++) grid[p[i].first][p[i].second] = 1;
        int pre = -1;
        for (i = 0; i < C; i++) {
            if (grid[0][i]) {
                if (pre != (i-1)) r1.pb(mp(pre+1,i-1));
                pre = i;
            }
        }
        if (pre != C-1) r1.pb(mp(pre+1,C-1));
        pre = -1;
        for (i = 0; i < C; i++) {
            if (grid[1][i]) {
                if (pre != (i-1)) r2.pb(mp(pre+1,i-1));
                pre = i;
            }
        }
        if (pre != C-1) r2.pb(mp(pre+1,C-1));
        pre = -1;
        for (i = 0; i < C; i++) {
            if (grid[0][i] && grid[1][i]) {
                if (pre != (i-1)) r12.pb(mp(pre+1,i-1));
                pre = i;
            }
        }
        if (pre != C-1) r12.pb(mp(pre+1,C-1));
    }
    else {
        for (i = 0; i < p.size(); i++) num[p[i].first].pb(p[i].second);
    }
}

struct seg { int y,l,r; };
int inter(seg a,seg b) {
    return !((a.r < b.l) || (a.l > b.r));
}
seg segs[400000];
vi adjList[400000];
int visited[400000];
int doDFS(int u) {
    if (visited[u]) return 0;
    int i;
    visited[u] = 1;
    for (i = 0; i < adjList[u].size(); i++) doDFS(adjList[u][i]);
    return 0;
}
int colour(int ar,int ac,int br,int bc) {
    ar--,ac--,br--,bc--;
    if (r == 2) {
        vpii *_use;
        if ((ar == 0) && (br == 0)) _use = &r1;
        else if ((ar == 0) && (br == 1)) _use = &r12;
        else _use = &r2;
        vpii &use = *_use;
        int l = lower_bound(use.begin(),use.end(),mp(ac,0))-use.begin()-1;
        if ((l == -1) || (use[l].second < ac)) l++;
        int r = upper_bound(use.begin(),use.end(),mp(bc,c))-use.begin()-1;
        return r-l+1;
    }

    int i,j;
    int t = 0;
    for (i = ar; i <= br; i++) {
        int pre = ac-1;
        int pt = t;
        for (j = 0; j < num[i].size(); j++) {
            if (num[i][j] > bc) break;
            if (num[i][j] >= ac) {
                if (pre != num[i][j]-1) segs[t++] = (seg){i,pre+1,num[i][j]-1};
                pre = num[i][j];
            }
        }
        if (pre != bc) segs[t++] = (seg){i,pre+1,bc};
        if (i > ar) {
            int t2 = pt-1;
            while ((t2 >= 0) && (segs[t2].y == i-1)) t2--;
            t2++;
            int k = t2;
            for (j = pt; j < t; j++) {
                while ((k < pt) && (segs[k].r < segs[j].l)) k++;
                while ((k < pt) && inter(segs[k],segs[j])) {
                    adjList[k].pb(j);
                    adjList[j].pb(k);
                    k++;
                }
                k--;
            }
        }
    }
    //for (i = 0; i <t;i++)cout<<segs[i].y<<","<<segs[i].l<<","<<segs[i].r<<endl;
    int ans = 0;
    fill(visited,visited+t,0);
    for (i = 0; i < t; i++) {
        if (!visited[i]) doDFS(i),ans++;
    }
    for (i = 0; i < t; i++) adjList[i].clear();
    return ans;
}

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

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:31:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < p.size(); i++) grid[p[i].first][p[i].second] = 1;
                     ~~^~~~~~~~~~
rainbow.cpp:58:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < p.size(); i++) num[p[i].first].pb(p[i].second);
                     ~~^~~~~~~~~~
rainbow.cpp: In function 'int doDFS(int)':
rainbow.cpp:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) doDFS(adjList[u][i]);
                 ~~^~~~~~~~~~~~~~~~~~~
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:95:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < num[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~~

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