开了 8e7 的 int 和 2e7 的 vector 会炸吧……
by robinyqc @ 2023-04-11 20:35:44
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define fr(i,l,r) for(int i=(l);i<=(r);i++)
#define eb emplace_back
#define ep emplace
template<typename T>inline T rd(T&a){
#define gc getchar
#define dg(x) (x>='0'&&x<='9')
char c=gc();T x=0,f=1;
for(;!dg(c);c=gc())if(c=='-')f=-1;
for(;dg(c);c=gc())x=(x<<1)+(x<<3)+c-48;
return a=f*x;
}template<typename T,typename...Val>void rd(T&x,Val&...val){rd(x),rd(val...);}
const int inf=0x3f3f3f3f,N=1e4+10;
const int dx[9]={-1,-1,-1,0,1,1,1,0},dy[9]={-1,0,1,1,1,0,-1,-1};
int n,R,C,x,y,t,num,top,cnt,ans=-inf;
vector<int> low,dfn,stk,c,sz,dis,f,in;
bool ins[N];
map<pii,int>id;
vector<vector<int> > gra,e;
vector<pii>ver;
void tarjan(int u){
low[u]=dfn[u]=++num,stk[++top]=u,ins[u]=1;
for(int v:gra[u])
if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
else if(ins[v])low[u]=min(low[u],dfn[v]);
if(low[u]==dfn[u]){++cnt;for(int v=0;u^v;)ins[v=stk[top--]]=0,c[v]=cnt,sz[cnt]+=dis[v];}
}
void topo(){
queue<int>q;
fr(i,1,cnt)if(f[i]=sz[i],!in[i])q.ep(i);
while(!q.empty()){
int u=q.front();q.pop();
for(int v:e[u])if(f[v]=max(f[v],f[u]+sz[v]),!--in[v])q.ep(v);
}
}
#define re resize(m)
int main(){
rd(n,R,C);
int m=n+R+C+1;
gra.resize(m,vector<int>()),e.resize(m,vector<int>());
low.re,
dfn.re,
stk.re,
c.re,
sz.re,
dis.re,
f.re,in.re;
// cout<<1;
fr(i,1,n){
int u=R+C+i;
rd(x,y,t),dis[u]=1,id[{x,y}]=i;
gra[x].eb(u),gra[R+y].eb(u);
switch(t){
case 1: gra[u].eb(x);break;
case 2: gra[u].eb(R+y);break;
case 3: ver.eb(x,y);
}
}
for(auto[x,y]:ver)fr(i,0,7){
int xx=x+dx[i],yy=y+dy[i];
auto it=id.find({xx,yy});
if(it!=id.end()){
auto[fi,se]=*it;
gra[R+C+id[{x,y}]].eb(R+C+se);
}
}
fr(i,1,R+C+n)if(!dfn[i])tarjan(i);
fr(u,1,R+C+n)for(int v:gra[u])if(c[u]^c[v])e[c[u]].eb(c[v]),in[c[v]]++;
topo();fr(i,1,cnt)ans=max(ans,f[i]);
return cout<<ans,0;
}
```
改成 vector 了。不保证常数，可能 TLE，可能 RE。还有需要您可以私信（另外我不是很会用 C++17 及以上版本）。
by robinyqc @ 2023-04-11 20:51:15
@[robinyqc](/user/338632) 谢谢，我看看
by AZN_0975 @ 2023-04-11 20:56:41
@[robinyqc](/user/338632) 您这份 40pts，而我那份把 N 改成 2.1e6 有 50pts
by AZN_0975 @ 2023-04-11 21:01:52
@[AZN_0975](/user/476985) 应该是 vector 效率原因。我最迟明天改出来优化的版本。
by robinyqc @ 2023-04-11 21:05:02
@[robinyqc](/user/338632) 谢谢 目前能拿到 50pts 的（我认为的）最优版本：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define fr(i,l,r) for(int i=(l);i<=(r);i++)
#define eb emplace_back
#define ep emplace
template<typename T>inline T rd(T&a){
#define gc getchar
#define dg(x) (x>='0'&&x<='9')
char c=gc();T x=0,f=1;
for(;!dg(c);c=gc())if(c=='-')f=-1;
for(;dg(c);c=gc())x=(x<<1)+(x<<3)+c-48;
return a=f*x;
}template<typename T,typename...Val>void rd(T&x,Val&...val){rd(x),rd(val...);}
const int inf=0x3f3f3f3f,N=2.1e6+10;
const int dx[9]={-1,-1,-1,0,1,1,1,0},dy[9]={-1,0,1,1,1,0,-1,-1};
int n,R,C,x,y,t,low[N],num,dfn[N],stk[N],top,c[N],cnt,sz[N],f[N],ans=-inf;
map<pii,int>id;
vector<int>gra[N],e[N];
vector<pii>ver;
void tarjan(int u){
low[u]=dfn[u]=++num,stk[++top]=u;
for(int v:gra[u])
if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
else if(!c[v])low[u]=min(low[u],dfn[v]);
if(low[u]==dfn[u]){
++cnt;
for(int v=0;u^v;)c[v=stk[top--]]=cnt,sz[cnt]+=v>R+C;
}
}
int main(){
rd(n,R,C);
fr(i,1,n){
int u=R+C+i;
rd(x,y,t),id[{x,y}]=i;
gra[x].eb(u),gra[R+y].eb(u);
switch(t){
case 1: gra[u].eb(x);break;
case 2: gra[u].eb(R+y);break;
case 3: ver.eb(x,y);
}
}
for(auto[x,y]:ver)fr(i,0,7){
int xx=x+dx[i],yy=y+dy[i];
auto it=id.find({xx,yy});
if(it!=id.end()){
auto[fi,se]=*it;
gra[R+C+id[{x,y}]].eb(R+C+se);
}
}
fr(i,1,R+C+n)if(!dfn[i])tarjan(i);
fr(u,1,R+C+n)for(int v:gra[u])if(c[u]^c[v])e[c[u]].eb(c[v]);
fr(i,1,cnt)f[i]=sz[i];
for(int u=cnt;u;u--)for(int v:e[u])f[v]=max(f[v],f[u]+sz[v]);
fr(i,1,cnt)ans=max(ans,f[i]);
return cout<<ans,0;
}
```
by AZN_0975 @ 2023-04-11 21:14:22
已经只剩 1.26e7 个 int 和 4.2e6 个 vector 了！
by AZN_0975 @ 2023-04-11 21:16:57
@[AZN_0975](/user/476985) 其实代码主要是慢在 vector 存图跑得很慢。您先试一下这份，不行我就改链式前向星。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define fr(i,l,r) for(int i=(l);i<=(r);i++)
#define eb emplace_back
#define ep emplace
template<typename T>inline T rd(T&a){
#define gc getchar
#define dg(x) (x>='0'&&x<='9')
char c=gc();T x=0,f=1;
for(;!dg(c);c=gc())if(c=='-')f=-1;
for(;dg(c);c=gc())x=(x<<1)+(x<<3)+c-48;
return a=f*x;
}template<typename T,typename...Val>void rd(T&x,Val&...val){rd(x),rd(val...);}
const int inf=0x3f3f3f3f,N=1e4+10;
const int dx[9]={-1,-1,-1,0,1,1,1,0},dy[9]={-1,0,1,1,1,0,-1,-1};
int n,R,C,x,y,t,num,top,cnt,ans=-inf;
int *low,*dfn,*stk,*c,*sz,*dis,*f,*in;
bool ins[N];
map<pii,int>id;
vector<vector<int> > gra,e;
vector<pii>ver;
void tarjan(int u){
low[u]=dfn[u]=++num,stk[++top]=u,ins[u]=1;
for(int v:gra[u])
if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
else if(ins[v])low[u]=min(low[u],dfn[v]);
if(low[u]==dfn[u]){++cnt;for(int v=0;u^v;)ins[v=stk[top--]]=0,c[v]=cnt,sz[cnt]+=dis[v];}
}
void topo(){
queue<int>q;
fr(i,1,cnt)if(f[i]=sz[i],!in[i])q.ep(i);
while(!q.empty()){
int u=q.front();q.pop();
for(int v:e[u])if(f[v]=max(f[v],f[u]+sz[v]),!--in[v])q.ep(v);
}
}
#define as new int[m+1]()
int main(){
rd(n,R,C);
int m=n+R+C;
gra.resize(m+1,vector<int>()),e.resize(m+1,vector<int>());
// int *low,*dfn,*stk,*c,*sz,*dis,*f,*in;
low=as,dfn=as,stk=as,c=as,sz=as,dis=as,f=as,in=as;
fr(i,1,n){
int u=R+C+i;
rd(x,y,t),dis[u]=1,id[{x,y}]=i;
gra[x].eb(u),gra[R+y].eb(u);
switch(t){
case 1: gra[u].eb(x);break;
case 2: gra[u].eb(R+y);break;
case 3: ver.eb(x,y);
}
}
for(auto[x,y]:ver)fr(i,0,7){
int xx=x+dx[i],yy=y+dy[i];
auto it=id.find({xx,yy});
if(it!=id.end()){
auto[fi,se]=*it;
gra[R+C+id[{x,y}]].eb(R+C+se);
}
}
fr(i,1,R+C+n)if(!dfn[i])tarjan(i);
fr(u,1,R+C+n)for(int v:gra[u])if(c[u]^c[v])e[c[u]].eb(c[v]),in[c[v]]++;
topo();fr(i,1,cnt)ans=max(ans,f[i]);
return cout<<ans,0;
}
```
by robinyqc @ 2023-04-11 21:33:38
我觉得还是很可能是 vector 存图跑得慢。我接着改改。
by robinyqc @ 2023-04-11 21:34:08
@[robinyqc](/user/338632) 但这是 MLE 不是 TLE 啊（
by AZN_0975 @ 2023-04-11 21:34:46