记录编号	594736	评测结果	MMMMMMMMMM
题目名称	宝藏	最终得分	0
用户昵称	darkMoon	是否通过	未通过
代码语言	C++	运行时间	0.009 s
提交时间	2024-10-04 18:50:30	内存使用	1.34 MiB

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
// auto IN = freopen("hzsotomon.in", "r", stdin);
// auto OUT = freopen("hzsotomon.out", "w", stdout);
auto mread = [](){int x;scanf("%d", &x);return x;};
const int N = 3e6 + 5;
int n = mread(), r = mread(), c = mread(), X[8] = {-1, -1, -1, 0, 0, 1, 1, 1}, Y[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int x[N], y[N], t[N];
int dfn[N], low[N], e[N], now, idx, sum[N], belong[N], f[N];
vector<int> gr[N];
vector<int> v[N], v2[N];
map<pair<int, int>, int> ap;
stack<int> st;
void tarjan(int x){
    dfn[x] = low[x] = ++idx;
    e[x] = 1;
    st.push(x);
    for(int y : v[x]){
        if(dfn[y] == 0){
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if(e[y]){
            low[x] = min(low[x], dfn[y]);
        }
    }
    if(low[x] == dfn[x]){
        now ++;
        while(st.top() != x){
            belong[st.top()] = now;
            if(st.top() <= n){
                sum[now] ++;
            }
            e[st.top()] = 0;
            st.pop();
        }
        belong[st.top()] = now;
        if(st.top() <= n){
            sum[now] ++;
        }
        e[st.top()] = 0;
        st.pop();
    }
}
signed main(){
    for(int i = 1; i <= n; i ++){
        cin >> x[i] >> y[i] >> t[i];
        v[n + x[i]].push_back(i);
        v[n + r + y[i]].push_back(i);
        if(t[i] == 1){
            v[i].push_back(n + x[i]);
        }
        else if(t[i] == 2){
            v[i].push_back(n + r + y[i]);
        }
        ap[mp(x[i], y[i])] = i;
    }
    for(int i = 1; i <= n; i ++){
        if(t[i] == 3){
            for(int j = 0; j < 8; j ++){
                int vx = x[i] + X[j], vy = y[i] + Y[j];
                if(ap.find(mp(vx, vy)) != ap.end()){
                    v[i].push_back(ap[mp(vx, vy)]);
                    printf("*** %d %d\n", i, ap[mp(vx, vy)]);
                }
            }
        }
    }
    for(int i = 1; i <= n + r + c; i ++){
        if(dfn[i] == 0){
            tarjan(i);
        }
    }
    for(int x = 1; x <= n + r + c; x ++){
        for(int y : v[x]){
            if(belong[x] != belong[y]){
                v2[belong[x]].push_back(belong[y]);
            }
        }
    }
    int ans = 0;
    for(int i = now; i >= 1; i --){
        f[i] = max(f[i], sum[i]);
        for(int j : v2[i]){
            f[j] = max(f[j], sum[j] + f[i]);
            ans = max(ans, f[j]);
        }
    }
    printf("%d", ans);
    return 0;
}