백준 20295 사탕 배달 혼내주기

 

 

 

아직 익숙하지 않아서 그런지, 아님 그냥 잔실수가 많아서 그런지 디버깅 하는데 많은 시간을 보냈다...
별도의 캔디 배열에 2i번 올라갈 때 마주치는 모든 캔디를 비트마스크로 저장해놓고 lca를 찾을 때 경로의 모든 캔디를 OR 연산한 뒤 쿼리로 필요한 캔디가 있는지 확인하면 된다.

번외로 질문 게시판에 반례가 없는 문제를 몇개 풀다보니 반례를 생각해보는 시간이 많아져서 강제로 실력이 느는 기분이다 ㅋㅋ. 역시 습관적 반례 검색은 실력에 도움이 안된다.

 

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(v) v.begin(), v.end()

int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

const int N = 17, MAX = 100001;
vector<int> adj[MAX];
int st[N][MAX], candies[N][MAX], depth[MAX], arr[MAX];
bool exist[6];
int n, m;

void input() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        int c; cin >> c;
        arr[i] = 1 << c;
        exist[c] = true;
    }
    for(int i = 0; i < n-1; ++i) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    cin >> m;
}

void bfs() {
    queue<pii> q;
    depth[1] = 1;
    q.push({1, 0});
    while(!q.empty()) {
        auto [from, d] = q.front(); q.pop();
        for(auto& to : adj[from]) {
            if(st[0][to] || to == 1) continue;
            st[0][to] = from;
            candies[0][to] |= arr[from];
            depth[to] = d+1;
            q.push({to, d+1});
        }
    }
}

bool lca(int u, int v, int c) {
    
    if(depth[u] < depth[v]) swap(u, v);
    int cand = arr[u] | arr[v];
    int diff = depth[u] - depth[v];
    for(int i = 0; i < N; ++i) {
        if(diff & (1 << i)) {
            cand |= candies[i][u];
            u = st[i][u];
        }
    }
    if(u == v) {
        if(cand & (1 << c)) return true;
        return false;
    }

    for(int i = N-1; i >= 0; --i) {
        if(st[i][u] != st[i][v]) {
            cand |= candies[i][u];
            cand |= candies[i][v];
            u = st[i][u], v = st[i][v];
        }
    }

    cand |= candies[0][u];
    cand |= candies[0][v];
    if(cand & (1 << c)) return true;
    return false;
}

int main() {
    fastio;
    input();

    bfs();

    for(int i = 1; i <= n; ++i) candies[0][i] |= arr[i];
    for(int i = 1; i < N; ++i) {
        for(int j = 1; j <= n; ++j) {
            st[i][j] = st[i-1][st[i-1][j]];
            candies[i][j] = candies[i-1][j] | candies[i-1][st[i-1][j]];
        }
    }

    m--;
    int ia, ib; cin >> ia >> ib;
    // 처음엔 사탕이 존재하면 play
    if(exist[ib]) cout << "PLAY\n";
    else cout << "CRY\n";
    int from = ia; 

    while(m--) {
        int to, candy; cin >> to >> candy;
        cout << (lca(from, to, candy) ? "PLAY\n" : "CRY\n");
        from = to;
    }
}