oj.uz

답안 #678667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
678667 2023-01-06T10:13:29 Z qwerasdfzxcl 무지개나라 (APIO17_rainbow) C++17
0 / 100
 20 ms 5076 KB 
#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int INF = 1e9+100;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dx8[9] = {-1, -1, -1, 0, 1, 1, 1, 0, -1}, dy8[9] = {-1, 0, 1, 1, 1, 0, -1, -1, -1};
set<pair<int, int>> st;
vector<int> S[3], E[3];
int n;

void init(int R, int C, int sr, int sc, int M, char *S) {
    st.emplace(sr, sc);

    for (int i=0;i<M;i++){
        int k;
        if (S[i]=='N') k = 0;
        if (S[i]=='E') k = 1;
        if (S[i]=='S') k = 2;
        if (S[i]=='W') k = 3;

        sr += dx[k], sc += dy[k];
        st.emplace(sr, sc);
    }

    auto iter = st.begin();
    for (int i=1;i<=2;i++){
        int prv = 1;
        while(iter!=st.end() && iter->first==i){
            if (iter->second > prv){
                ::S[i].push_back(prv);
                E[i].push_back(iter->second-1);
                //ran.emplace_back(prv, iter->second-1);
                //printf("ran: %d %d\n", prv, iter->second-1);
            }
            prv = iter->second+1;
            ++iter;
        }

        if (prv<=C){
            ::S[i].push_back(prv);
            E[i].push_back(C);
            //printf("ran: %d %d\n", prv, C);
        }
    }

    n = C;
}

bool valid(int x, int y, int ar, int ac, int br, int bc){
    if (st.find(make_pair(x, y))!=st.end()) return 0;
    return ar <= x && x <= br && ac <= y && y <= bc;
}

void add_edge(int x1, int y1, int x2, int y2, set<pair<int, int>> &V, map<pair<int, int>, vector<pair<int, int>>> &E, int ar, int ac, int br, int bc){
    if (valid(x1, y1, ar, ac, br, bc)) V.emplace(x1, y1);
    if (valid(x2, y2, ar, ac, br, bc)) V.emplace(x2, y2);

    if (!valid(x1, y1, ar, ac, br, bc)) return;
    if (!valid(x2, y2, ar, ac, br, bc)) return;

    auto p1 = make_pair(x1, y1);
    auto p2 = make_pair(x2, y2);
    E[p1].push_back(p2);
    E[p2].push_back(p1);

    //printf("add_edge: %d %d %d %d\n", x1, y1, x2, y2);
}

void dfs(int x, int y, map<pair<int, int>, vector<pair<int, int>>> &E, set<pair<int, int>> &visited){
    visited.emplace(x, y);
    auto p = make_pair(x, y);
    for (auto np:E[p]) if (visited.find(np)==visited.end()){
        dfs(np.first, np.second, E, visited);
    }
}

int colour(int ar, int ac, int br, int bc) {
    int cnt[3];
    for (int i=1;i<=2;i++){
        cnt[i] = (upper_bound(S[i].begin(), S[i].end(), bc) - S[i].begin()) - (lower_bound(E[i].begin(), E[i].end(), ac) - E[i].begin());
        cnt[i] = max(cnt[i], 0);
    }

    if (ar==br) return cnt[ar];
    int ans = cnt[1] + cnt[2];
    if (!S[1].empty() && !S[2].empty()){
        if (S[1][0]==1 && S[2][0]==1 && E[1][0] >= ac && E[1][1] >= ac) ans--;
        if (E[1].back()==n && E[2].back()==n && S[1].back() <= bc && E[1].back() <= bc) ans--;
    }

    return ans;


    /*if (br <= st.begin()->first-1) return 1;
    ar = max(ar, st.begin()->first-1);
    set<pair<int, int>> V, visited;
    map<pair<int, int>, vector<pair<int, int>>> E;

    for (int i=ar;i<=br;i++){
        add_edge(i, ac, i+1, ac, V, E, ar, ac, br, bc);
        add_edge(i, bc, i+1, bc, V, E, ar, ac, br, bc);
    }

    for (int j=ac;j<=bc;j++){
        add_edge(ar, j, ar, j+1, V, E, ar, ac, br, bc);
        add_edge(br, j, br, j+1, V, E, ar, ac, br, bc);
    }

    for (auto [x, y]:st){
        for (int k=0;k<8;k++){
            int nx1 = x + dx8[k], ny1 = y + dy8[k];
            int nx2 = x + dx8[k+1], ny2 = y + dy8[k+1];

            add_edge(nx1, ny1, nx2, ny2, V, E, ar, ac, br, bc);
        }
    }

    int ret = 0;
    for (auto &[x, y]:V) if (visited.find(make_pair(x, y))==visited.end()) {dfs(x, y, E, visited); ret++;}
    return ret;*/
}

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:23:32: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   23 |         sr += dx[k], sc += dy[k];
      |                            ~~~~^

Subtask #1
0 / 11.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 18 ms 5076 KB Output is correct
3 Correct 20 ms 4976 KB Output is correct
4 Incorrect 20 ms 4976 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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