@[songhaoran](/space/show?uid=80679) 我好像就没有排序
by ecnerwaIa @ 2019-03-14 20:23:34
@[songhaoran](/space/show?uid=80679) ```cpp
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
map<int,int>lx,ly;
int cnt,py[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1}};
const int N=410000,M=110000;
struct node{
int opt,x,y;
}t[M];
int n,r,c,to[N],nxt[N],d[N];
int tot;
inline void ins(int a,int b){
to[++tot]=b;
nxt[tot]=d[a];
d[a]=tot;
}
int dfn[N],st[N],id[N],size[N],dfstime,low[N],cl;
bool instack[N];
inline void tarjan(int x){
dfn[x]=low[x]=++dfstime;
st[++st[0]]=x;
instack[x]=1;
for(int i=d[x];i;i=nxt[i]){
int u=to[i];
if(instack[u]){
low[x]=min(low[x],dfn[u]);
}
else{
if(!dfn[u]){
tarjan(u);
low[x]=min(low[x],low[u]);
}
}
}
if(dfn[x]==low[x]){
++cl;
int k;
do{
k=st[st[0]--];
id[k]=cl;
instack[k]=0;
if(k<=n)size[cl]++;
}while(k!=x);
}
}
int to_2[N],nxt_2[N],d_2[N],tot_2,rd[N],dp[N],ans;
inline void ins_2(int a,int b){
to_2[++tot_2]=b;
nxt_2[tot_2]=d_2[a];
d_2[a]=tot_2;
}
struct wjr{
int head[50100],val[100100],id[100100],nt[100100],cnt;
}g[2];
const int hash=50000;
inline int gets(int val,int now){
int p=(val%hash)+1;
for(int i=g[now].head[p];i;i=g[now].nt[i]){
if(val==g[now].val[i]){
return g[now].id[i];
}
}
g[now].nt[++g[now].cnt]=g[now].head[p];
int num=g[now].cnt;
g[now].head[p]=num;
g[now].val[num]=val;
g[now].id[num]=++cnt;
return cnt;
}
struct wjr_2{
int head[50010],nt[100100],cnt,id[100100];
long long val[100100];
}w;
inline void ins_hash(long long v,int num){
int p=v%hash+1;
w.nt[++w.cnt]=w.head[p];
w.head[p]=w.cnt;
w.val[w.cnt]=v;
w.id[w.cnt]=num;
}
inline int get_hash(long long v){
int p=v%hash+1;
for(int i=w.head[p];i;i=w.nt[i]){
if(v==w.val[i]){
return w.id[i];
}
}
return 0;
}
int main(){
scanf("%d%d%d",&n,&r,&c);
cnt=n;
for(int i=1;i<=n;++i){
scanf("%d%d%d",&t[i].x,&t[i].y,&t[i].opt);
int rx=gets(t[i].x,0),ry=gets(t[i].y,1);
ins(rx,i);
ins(ry,i);
if(t[i].opt==1){
ins(i,rx);
}
if(t[i].opt==2){
ins(i,ry);
}
ins_hash((t[i].x-1ll)*1ll*c+(t[i].y),i);
}
for(int i=1;i<=n;++i){
if(t[i].opt!=3)continue;
for(int j=0;j<8;++j){
int nx=t[i].x+py[j][0],ny=t[i].y+py[j][1];
int g=get_hash((nx-1ll)*1ll*c+ny);
if(g)ins(i,g);
}
}
for(int i=1;i<=cnt;++i)if(!dfn[i])tarjan(i);
for(int i=1;i<=cnt;++i){
for(int j=d[i];j;j=nxt[j]){
int u=to[j];
if(id[u]!=id[i]){
ins_2(id[i],id[u]);
rd[id[u]]++;
}
}
}
int l=1,r=0;
for(int i=1;i<=cl;++i){
if(!rd[i])st[++r]=i;
dp[i]=size[i];
}
while(r>=l){
int x=st[l++];
ans=max(ans,dp[x]);
for(int i=d_2[x];i;i=nxt_2[i]){
int u=to_2[i];
rd[u]--;
dp[u]=max(dp[u],dp[x]+size[u]);
if(!rd[u])st[++r]=u;
}
}
printf("%d\n",ans);
return 0;
}
```
by ecnerwaIa @ 2019-03-14 20:24:45
```cpp
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
map<int,int>lx,ly;
int cnt,py[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1}};
const int N=410000,M=110000;
struct node{
int opt,x,y;
}t[M];
int n,r,c,to[N],nxt[N],d[N];
int tot;
inline void ins(int a,int b){
to[++tot]=b;
nxt[tot]=d[a];
d[a]=tot;
}
int dfn[N],st[N],id[N],size[N],dfstime,low[N],cl;
bool instack[N];
inline void tarjan(int x){
dfn[x]=low[x]=++dfstime;
st[++st[0]]=x;
instack[x]=1;
for(int i=d[x];i;i=nxt[i]){
int u=to[i];
if(instack[u]){
low[x]=min(low[x],dfn[u]);
}
else{
if(!dfn[u]){
tarjan(u);
low[x]=min(low[x],low[u]);
}
}
}
if(dfn[x]==low[x]){
++cl;
int k;
do{
k=st[st[0]--];
id[k]=cl;
instack[k]=0;
if(k<=n)size[cl]++;
}while(k!=x);
}
}
int to_2[N],nxt_2[N],d_2[N],tot_2,rd[N],dp[N],ans;
inline void ins_2(int a,int b){
to_2[++tot_2]=b;
nxt_2[tot_2]=d_2[a];
d_2[a]=tot_2;
}
struct wjr{
int head[50100],val[100100],id[100100],nt[100100],cnt;
}g[2];
const int hash=50000;
inline int gets(int val,int now){
int p=(val%hash)+1;
for(int i=g[now].head[p];i;i=g[now].nt[i]){
if(val==g[now].val[i]){
return g[now].id[i];
}
}
g[now].nt[++g[now].cnt]=g[now].head[p];
int num=g[now].cnt;
g[now].head[p]=num;
g[now].val[num]=val;
g[now].id[num]=++cnt;
return cnt;
}
struct wjr_2{
int head[50010],nt[100100],cnt,id[100100];
long long val[100100];
}w;
inline void ins_hash(long long v,int num){
int p=v%hash+1;
w.nt[++w.cnt]=w.head[p];
w.head[p]=w.cnt;
w.val[w.cnt]=v;
w.id[w.cnt]=num;
}
inline int get_hash(long long v){
int p=v%hash+1;
for(int i=w.head[p];i;i=w.nt[i]){
if(v==w.val[i]){
return w.id[i];
}
}
return 0;
}
int main(){
scanf("%d%d%d",&n,&r,&c);
cnt=n;
for(int i=1;i<=n;++i){
scanf("%d%d%d",&t[i].x,&t[i].y,&t[i].opt);
int rx=gets(t[i].x,0),ry=gets(t[i].y,1);
ins(rx,i);
ins(ry,i);
if(t[i].opt==1){
ins(i,rx);
}
if(t[i].opt==2){
ins(i,ry);
}
ins_hash((t[i].x-1ll)*1ll*c+(t[i].y),i);
}
for(int i=1;i<=n;++i){
if(t[i].opt!=3)continue;
for(int j=0;j<8;++j){
int nx=t[i].x+py[j][0],ny=t[i].y+py[j][1];
int g=get_hash((nx-1ll)*1ll*c+ny);
if(g)ins(i,g);
}
}
for(int i=1;i<=cnt;++i)if(!dfn[i])tarjan(i);
for(int i=1;i<=cnt;++i){
for(int j=d[i];j;j=nxt[j]){
int u=to[j];
if(id[u]!=id[i]){
ins_2(id[i],id[u]);
rd[id[u]]++;
}
}
}
int l=1,r=0;
for(int i=1;i<=cl;++i){
if(!rd[i])st[++r]=i;
dp[i]=size[i];
}
while(r>=l){
int x=st[l++];
ans=max(ans,dp[x]);
for(int i=d_2[x];i;i=nxt_2[i]){
int u=to_2[i];
rd[u]--;
dp[u]=max(dp[u],dp[x]+size[u]);
if(!rd[u])st[++r]=u;
}
}
printf("%d\n",ans);
return 0;
}
```
by ecnerwaIa @ 2019-03-14 20:24:57
~~去你的萌新~~
by Limit @ 2019-03-14 20:25:09
这题貌似是并查集，反正我不会
by Limit @ 2019-03-14 20:25:31
@[Sxy_Limit](/space/show?uid=86625) 这题不是拓扑排序+tarjan吗？
by ecnerwaIa @ 2019-03-14 20:26:24
我弱呀，记得老师说是并查集
by Limit @ 2019-03-14 20:27:53
这题改了数据吗？为什么我交以前的AC代码RE了...
by ecnerwaIa @ 2019-03-14 20:29:26
@[Sxy_Limit](/space/show?uid=86625) 并查集？
by ecnerwaIa @ 2019-03-14 20:30:22
@[千年之狐_天才](/space/show?uid=54113) ~~我记得貌似是这样的QAQ~~
您能AC说明您强，我不会说明我弱
by Limit @ 2019-03-14 20:33:02