oj.uz

답안 #59359

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
59359 2018-07-21T19:04:29 Z duality 무지개나라 (APIO17_rainbow) C++11
12 / 100
 157 ms 28588 KB 
#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;
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 14456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 14468 KB Output is correct
2 Correct 15 ms 14528 KB Output is correct
3 Correct 111 ms 18824 KB Output is correct
4 Correct 121 ms 19612 KB Output is correct
5 Correct 130 ms 19752 KB Output is correct
6 Correct 153 ms 19752 KB Output is correct
7 Correct 157 ms 19908 KB Output is correct
8 Correct 113 ms 19908 KB Output is correct
9 Correct 114 ms 19908 KB Output is correct
10 Correct 139 ms 19908 KB Output is correct
11 Correct 135 ms 19908 KB Output is correct
12 Correct 130 ms 19908 KB Output is correct
13 Correct 91 ms 19908 KB Output is correct
14 Correct 104 ms 19972 KB Output is correct
15 Correct 112 ms 19972 KB Output is correct
16 Correct 114 ms 19972 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 19972 KB Output is correct
2 Correct 49 ms 25752 KB Output is correct
3 Correct 52 ms 28588 KB Output is correct
4 Correct 73 ms 28588 KB Output is correct
5 Incorrect 47 ms 28588 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 14456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 14456 KB Output isn't correct
2 Halted 0 ms 0 KB -