QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#111539 | #6502. Disjoint Set Union | AFewSuns | WA | 88ms | 3756kb | C++14 | 2.9kb | 2023-06-07 15:41:10 | 2023-06-07 15:41:11 |
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();
while(t--){
n=read();
fr(i,1,n) fa[i]=read();
fr(i,1,n) g[i]=read();
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");
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: 3648kb
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: 88ms
memory: 3756kb
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 4 1 1 1 5 2 1 2 1 5 YES 0 YES 13 1 2 1 3 1 4 1 5 2 3 4 1 2 1 4 1 5 2 2 4 1 4 1 5 2 4 1 1 5 YES 4 1 3 1 5 2 3 2 1 5 YES 0 YES 5 1 1 1 2 2 1 5 1 2 2 2 3 YES 9 1 2 1 3 1 5 2 5 4 1 2 1 3 2 2 4 1 3 2 3 1 YES 2 1 5 2 5 2 YES 2 1 2 2 2 3 YES 7 1 1 1 3 1 5 2 3 4 1 1 1 5 2 1 2 YES 2 1 1 2 1 5 YES 8 1 1 1...
result:
wrong answer you didn't find a solution but jury did (test case 18)