- 一方通行（accelerator）
Hack tomxi 的代码
-
lllz
@
2024-8-10 12:04:12
tomxi 的代码：
#include<bits/stdc++.h>
using namespace std;
#define up(i,l,r) for(int i=l;i<=r;++i)
#define dn(i,l,r) for(int i=r;i>=l;--i)
const int N=1e5+5;
const int K=12;
int n,k,a[N],m,dp[N][K],in[N];
vector<int> g[N];
int main(){
freopen("accelerator.in","r",stdin);
freopen("accelerator.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>m>>k;
up(i,1,n) cin>>a[i];
up(i,1,m){
int u,v;
cin>>u>>v;
g[u].push_back(v);
in[v]++;
}
queue<int> q;
up(i,1,n){
up(j,1,k){
dp[i][j]=0;
}
dp[i][a[i]]=1;
}
q.push(1);
dp[1][a[1]]=1;
while(q.size()){
int u=q.front();q.pop();
for(auto v:g[u]){
--in[v];
up(j,1,k){
dp[v][j]=max(dp[v][j],dp[u][j]);
}
dp[v][a[v]]=max(dp[v][a[v]],dp[u][a[v]]+1);
if(!in[v]){
q.push(v);
}
}
}
int mx=0;
up(i,1,n){
up(j,1,k){
mx=max(mx,dp[i][j]);
}
}
cout<<mx;
return 0;
}
//tomxi
Hack 数据：
4 3 1
1 1 1 1
1 3
2 3
3 4
答案为 ，tomxi 输出了 。
2 条评论
-
Zoomy 小数据结构 SU @ 2024-8-10 15:19:03已修改#include<bits/stdc++.h> using namespace std; int n,m,k,a[100005],dp[100005][15],in[100005],ans; bool SubTask1=1,SubTask2=1; queue<int> Q; struct Graph { int hd[100005],tot,to[500005],nxt[500005]; void add(int F,int T) { ++tot; to[tot]=T; nxt[tot]=hd[F]; hd[F]=tot; } }G; signed main() { // freopen("accelerator.in","r",stdin); // freopen("accelerator.out","w",stdout); cin>>n>>m>>k; for(int i=1;i<=n;++i) cin>>a[i]; for(int i=1;i<=m;++i) { int u,v; cin>>u>>v; G.add(u,v); ++in[v]; if(u!=1||v!=i) SubTask1=0; if(u!=i||v!=i+1) SubTask2=0; } // ---------------------------------------------------------------- if(n==2) { if(a[1]==a[2]) cout<<2; else cout<<1; return 0; } // ---------------------------------------------------------------- if(SubTask1) { for(int i=2;i<=n;++i) if(a[1]==a[i]) { cout<<2; return 0; } cout<<1; return 0; } // ---------------------------------------------------------------- if(SubTask2) { int bak[k+1],ans=0; for(int i=1;i<=k;++i) bak[i]=0; for(int i=1;i<=n;++i) ++bak[a[i]]; for(int i=1;i<=k;++i) ans=max(ans,bak[i]); cout<<ans; return 0; } // ---------------------------------------------------------------- for(int i=2;i<=n;++i) if(!in[i]) Q.push(i); while(Q.size()) { int x=Q.front(); Q.pop(); for(int i=G.hd[x];i;i=G.nxt[i]) { int to=G.to[i]; --in[to]; if(!in[to]) Q.push(to); } } // ---------------------------------------------------------------- Q.push(1); dp[1][a[1]]=1; while(Q.size()) { int x=Q.front(); Q.pop(); for(int i=G.hd[x];i;i=G.nxt[i]) { int to=G.to[i]; --in[to]; if(!in[to]) Q.push(to); for(int p=1;p<=k;++p) dp[to][p]=max(dp[to][p],dp[x][p]+(a[to]==p)); } } for(int i=1;i<=n;++i) for(int p=1;p<=k;++p) ans=max(ans,dp[i][p]); cout<<ans; return (0^0); }这是本题 std，数据只是题意的一个子集，并不保证全面地覆盖所有情况，因而数据水并不算做题目的错误。对于多个无入度点的情况，确实能 hack tomxi 同学，但 hack 不了 std。
如果说数据水，这个我承认。对于 2023 级甚至 2024 级的同学，在图上进行操作的难度不是一星半点，所以造数据的时候故意缩小了范围。数据水不止体现在这一方面，还体现在放过
已死的SPFA，还体现在让加了剪枝的搜索取得 90 分。毕竟这是普及组模拟赛。
-
@ 2024-8-10 13:27:42
澄清： 我的代码确实有问题，但是对于数据来说没问题，数据保证了只有1是源点，根据题意，重写：https://loioj.cn/record/66b6f95b7214b5515aaab31c 份代码，能AC也能过hack
- 1