uva 11994번 Happy Painting!

uva : https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3145

 

espa에서는 괜찮은데 uva에서 제출해봤는데 TLE가 뜬다..

아무래도 소스가 lct나 splay를 쓰지않은 탐색코드이고 espa의 tc가 uva보다 약하기 때문인 것 같은데

lct ? splay를 공부해서 제출해봐야겠다.

 

지금 소스는 espa에서는 빠르게 통과되는 코드로

type2, 3번의 시간을 최대한 단축시키기 위해서

height 높이 개념을 이용했다.

 

LCA를 알면 좀더 빠르게 해결할 수 있다는데 뭐 통과는 되니까 일단 올려놓고

고급 자료구조를 공부한 후에 다시 적용해봐야겠다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
#include <string>
using namespace std;
 
struct NODE {
    int root = -1;
    int pn = -1;
    int pn_color = -1;
    int height = -1;
    struct pii {
        int num;
        int color;
    };
    vector<pii> other;
}node[50001];
 
bool visit[50001];
bool color_arr[31];
int inn, inm;
int join = 0;
int answer_edge, answer_color;
 
int check_tree(int x) {
    answer_edge++;
    if (color_arr[node[x].pn_color] == false) {
        answer_color++;
        color_arr[node[x].pn_color] = true;
    }
 
    return node[x].pn;
}
 
void make_height2(int x, int y) {
    memset(color_arr, 0, sizeof(color_arr));
    while (node[x].height != node[y].height) {
        if (node[x].height > node[y].height) x = check_tree(x);
        else y = check_tree(y);
    }
    if (x != y) {
        while (x != y) {
            x = check_tree(x);
            y = check_tree(y);
        }
    }
}
 
int color_change(int x, int c) {
    for (int i = 0; i < node[node[x].pn].other.size(); i++) {
        if (node[node[x].pn].other[i].num == x) {
            node[node[x].pn].other[i].color = c;
            break;
        }
    }
    node[x].pn_color = c;
    return node[x].pn;
}
 
void make_height(int x, int y, int c) {
    while (node[x].height != node[y].height) {
        if (node[x].height > node[y].height) x = color_change(x, c);
        else y = color_change(y, c);
    }
 
    if (x != y) {
        while (x != y) {
            x = color_change(x, c);
            y = color_change(y, c);
        }
    }
}
 
void delete_node(int x, int y) {
    for (int i = 0; i < node[x].other.size(); i++) {
        if (node[x].other[i].num == y) {
            node[x].other.erase(node[x].other.begin() + i, node[x].other.begin() + i + 1);
            break;
        }
    }
}
 
void change_father(int x, int y, int c) {
    if (node[x].root != x)    delete_node(node[x].pn, x);
 
    node[y].other.push_back({ x, c });
    node[x].pn_color = c;
 
    queue<pair<pair<int,int>,int> > q;
    q.push({ {x,y},node[y].height });
 
    while (!q.empty()) {
        int temp = q.front().first.first;
        int p = q.front().first.second;
        int h = q.front().second;
        q.pop();
 
        node[temp].root = node[y].root;
        node[temp].pn = p;
        node[temp].height = h + 1;
        for (int i = 0; i < node[temp].other.size(); i++) {
            q.push({{ node[temp].other[i].num, temp}, h+1});
        }
    }
}
 
bool check_father(int x, int y) {
    if (x == y) return true;
    if (node[x].root == x) return false;
    return check_father(node[x].pn, y);
}
 
void insert_node(int num, int parent, int color) {
    if (parent == 0) { // root
        visit[num] = true;
        node[num].height = 0;
        node[num].pn = num;
        node[num].root = num;
        join++;
        return;
    }
 
    if (node[parent].root == -1) return;
    if (visit[num]) {
        join++;
        return;
    }
 
    visit[num] = true;
    node[num].root = node[parent].root;
    node[num].pn = parent;
    node[num].pn_color = color;
    node[num].height = node[parent].height + 1;
    node[parent].other.push_back({ num, color });
    join++;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    vector<pair<pair<int, int>, int> > in;
    cin >> inn >> inm;
 
    for (int i = 1; i <= inn; i++) {
        int num;
        cin >> num;
        in.push_back({ {num,0},i });
    }
    for (int i = 0; i < inn; i++) {
        int col;
        cin >> col;
        in[i].first.second = col;
    }
    sort(in.begin(), in.end());
 
    while (join != inn) {
        join = 0;
        for (int i = 0; i < inn; i++)
            insert_node(in[i].second, in[i].first.first, in[i].first.second);
    }
    for (int i = 1; i <= inn; i++) visit[i] = 0;
 
    while (inm--) {
        int type, x, y, c;
        cin >> type >> x >> y;
        if (type == 1) {
            cin >> c;
            if (x == y) continue;
            if (node[x].root != node[y].root) change_father(x, y, c);
            else {
                if (!check_father(y, x)) change_father(x, y, c);
            }
        }
        if (type == 2) {
            cin >> c;
            if (x == y || node[x].root != node[y].root) continue;
            make_height(x, y, c);
        }
        if (type == 3) {
            if (x == y || node[x].root != node[y].root)
                cout << "0 0\n";
            else {
                answer_edge = answer_color = 0;
                make_height2(x, y);
                cout << answer_edge << " " << answer_color << "\n";
            }
        }
    }
}