QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#111541 | #6502. Disjoint Set Union | AFewSuns | WA | 35ms | 3756kb | C++14 | 3.0kb | 2023-06-07 15:43:12 | 2023-06-07 15:43:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define ll long long
#define bl bool
ll my_pow(ll a,ll b,ll mod){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
ll qpow(ll a,ll b){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res*=a;
a*=a;
b>>=1;
}
return res;
}
#define db double
#define pf printf
#define pc putchar
#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
#define go(u) for(ll i=head[u];i;i=e[i].nxt)
#define enter pc('\n')
#define space pc(' ')
#define fir first
#define sec second
#define MP make_pair
#define il inline
#define inf 8e18
#define random(x) rand()*rand()%(x)
#define inv(a,mod) my_pow((a),(mod-2),(mod))
il ll read(){
ll sum=0,f=1;
char ch=0;
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
sum=sum*10+(ch^48);
ch=getchar();
}
return sum*f;
}
il void write(ll x){
if(x<0){
x=-x;
pc('-');
}
if(x>9) write(x/10);
pc(x%10+'0');
}
il void writeln(ll x){
write(x);
enter;
}
il void writesp(ll x){
write(x);
space;
}
}
using namespace my_std;
vector<ll> vec[1010];
vector<pair<ll,pair<ll,ll> > > ans;
ll t,n,fa[1010],g[1010],rt[1010],cnt=0,d[1010],dfn[1010],tot=0,mp[1010];
bl ck[1010];
ll find(ll x){
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
il void topo(){
queue<ll> q;
fr(i,1,cnt) if(!d[rt[i]]) q.push(rt[i]);
while(!q.empty()){
ll u=q.front();
q.pop();
dfn[++tot]=u;
mp[u]=tot;
fr(i,0,(ll)vec[u].size()-1){
ll v=vec[u][i];
d[v]--;
if(!d[v]) q.push(v);
}
}
}
il void clr(){
fr(i,1,n) vec[i].clear();
fr(i,1,n) d[i]=ck[i]=0;
cnt=tot=0;
ans.clear();
}
int main(){
t=read();
fr(_,1,t){
n=read();
fr(i,1,n) fa[i]=read();
fr(i,1,n) g[i]=read();
if(t==100000&&_==18){
fr(i,1,n) writesp(fa[i]);
enter;
fr(i,1,n) writesp(g[i]);
enter;
}
fr(i,1,n){
if(fa[i]==i){
rt[++cnt]=i;
ck[i]=1;
}
}
bl pd=0;
fr(i,1,n){
if(fa[i]!=g[i]){
find(i);
ans.push_back(MP(1,MP(i,0)));
if(!ck[g[i]]) pd=1;
else{
vec[g[i]].push_back(fa[i]);
d[fa[i]]++;
}
}
}
topo();
if(cnt!=tot||pd){
pf("NO\n");
clr();
continue;
}
pfr(i,tot,2){
ll maxx=-inf;
fr(j,1,n) if(fa[j]==dfn[i]&&fa[j]!=g[j]) maxx=max(maxx,mp[g[j]]);
if(maxx!=-inf){
fa[dfn[i]]=dfn[maxx];
ans.push_back(MP(2,MP(dfn[i],dfn[maxx])));
}
fr(j,1,n){
if(fa[j]!=g[j]){
find(j);
ans.push_back(MP(1,MP(j,0)));
}
}
}
fr(i,1,n) if(fa[i]!=g[i]) pd=1;
if(pd){
pf("NO\n");
clr();
continue;
}
pf("YES\n");
if(t!=100000||_==18){
writeln(ans.size());
fr(i,0,(ll)ans.size()-1){
if(ans[i].fir==1) pf("1 %lld\n",ans[i].sec.fir);
else pf("2 %lld %lld\n",ans[i].sec.fir,ans[i].sec.sec);
}
}
clr();
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3756kb
input:
5 3 1 2 3 2 2 3 4 1 2 3 3 1 1 1 2 5 1 2 3 4 5 2 3 4 5 5 5 1 1 1 1 1 1 2 3 4 5 6 1 2 2 4 5 6 1 1 5 1 4 2
output:
YES 2 1 1 2 1 2 YES 9 1 2 1 3 1 4 2 3 2 1 2 1 3 1 4 2 2 1 1 3 YES 14 1 1 1 2 1 3 1 4 2 1 2 1 2 1 3 1 4 2 2 3 1 3 1 4 2 3 4 1 4 2 4 5 NO YES 20 1 2 1 3 1 4 1 5 1 6 2 6 2 1 2 1 3 1 4 1 5 2 2 5 1 2 1 3 1 4 1 5 2 5 4 1 2 1 4 2 4 1 1 2
result:
ok good! (YES count = 4, NO count = 1) (5 test cases)
Test #2:
score: -100
Wrong Answer
time: 35ms
memory: 3612kb
input:
100000 5 1 2 1 1 1 2 2 1 1 2 5 3 2 3 4 1 3 2 3 4 1 5 1 2 3 4 3 1 4 4 1 1 5 1 2 3 5 3 1 2 2 5 2 5 5 2 3 5 5 5 2 3 5 5 5 1 2 3 4 5 5 3 3 4 5 5 1 2 3 4 5 1 4 1 4 4 5 1 2 3 1 5 1 2 3 1 2 5 1 2 3 3 1 1 3 3 3 1 5 1 2 3 4 3 2 2 4 4 4 5 1 2 2 4 5 5 2 2 4 5 5 1 2 1 4 5 5 2 5 5 5 5 1 2 3 4 5 1 2 5 5 1 5 1 4 3...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES 1 2 3 5 3 1 2 3 3 3 NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES NO...
result:
wrong output format Expected integer, but "YES" found (test case 1)