QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#373645 | #6502. Disjoint Set Union | 514imba | WA | 1ms | 3824kb | C++11 | 2.9kb | 2024-04-01 21:20:35 | 2024-04-01 21:20:37 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define MP make_pair
using namespace std;
typedef long long ll;
template<typename T> void read( T &r ) {
r=0; bool w=false; char ch=getchar();
while( ch < '0' || ch > '9' ) w = !(ch^45), ch = getchar();
while( ch >= '0' && ch <= '9' ) r = (r<<1) + (r<<3) + (ch^48), ch = getchar();
r = w ? -r : r;
}
#define MAXN 1000
int n, fsonvis[MAXN+5], f[MAXN+5], g[MAXN+5], frt[MAXN+5];
int fa[2][MAXN+5], in[MAXN+5];
vector<int> to[MAXN+5];
int find( int x, int idx = 0 ) {
if( fa[idx][x] == x ) return x;
return fa[idx][x] = find(fa[idx][x],idx);
}
void unite( int x , int y, int idx = 0 ) {
x = find(x,idx), y = find(y,idx);
fa[idx][x] = y;
}
void add( int u , int v ) {
++in[v]; to[u].pb(v);
}
queue<int> q; int arr[MAXN+5];
int st[2][MAXN+5];vector<int> cl[MAXN+5];
struct ansNode{
int x, y;
}ans[MAXN*MAXN*2+5];int anstot;
bool topo( int rt ){
while( !q.empty() ) q.pop(); arr[0] = 0;
for(int i=1;i<=n;i++) if( find(i,1) == rt && !in[i] && frt[i] ) q.push(i);
while( !q.empty() ) {
int u = q.front(); q.pop(); arr[++arr[0]] = u;
for(auto v: to[u]) if( --in[v] == 0 ) q.push(v);
}
for(int i=1;i<=n;i++) if( find(i,1) == rt && in[i] ) return false;
#define st1 st[x]
#define st2 st[x^1]
int x = 0; st2[0] = 0;
st1[st1[0]=1]=arr[1]; for(auto i: cl[arr[1]]) st1[++st1[0]] = i;
x^=1;
for(int i=2;i<=arr[0];i++) {
st1[st1[0]=1] = arr[i];
for(auto v: cl[arr[i]]) st1[++st1[0]] = v;
for(int j=1;j<=st2[0];j++) {
ans[++anstot] = {st2[j], arr[i]};
if( g[st2[j]] != arr[i] ) st1[++st1[0]] = st2[j];
}
x^=1;
}
return true;
}
int topovis[MAXN+5];
void solve() {
read(n); anstot = 0;
for(int i=1;i<=n;i++) fa[0][i] = fa[1][i] = i, to[i].clear(), cl[i].clear(),
fsonvis[i] = false, frt[i] = false, in[i]=0, topovis[i]=false;
for(int i=1;i<=n;i++) read(f[i]), unite(i,f[i]), fsonvis[f[i]] = true;
for(int i=1;i<=n;i++) if( find(i) == i ) frt[i] = true;
for(int i=1;i<=n;i++) {
read(g[i]);
if( f[i] != g[i] && !frt[g[i]] ) { puts("NO"); return; }
if( find(i) != find(g[i]) ) add(find(i),g[i]);
unite(i,g[i],1);
}
for(int i=1;i<=n;i++) {
if( find(i,1) != find(f[i],1) ) { puts("NO"); return; }
if( !fsonvis[i] && !frt[i] ) {
bool chg = false;
for(int p=i;!frt[p];p=f[p]) {
if( f[p] != g[p] ) {
chg = true;
if( !frt[f[p]] ) ans[++anstot] = { p, find(p,0) };
cl[find(p)].pb(p);
}
else if( chg && !frt[f[p]] ) { puts("NO"); return; }
}
}
}
for(int i=1;i<=n;i++) {
if( !topovis[find(i,1)] ) {
if( !topo(find(i,1)) ) { puts("NO"); return; }
topovis[find(i,1)] = true;
}
}
puts("YES"); printf("%d\n",anstot);
for(int i=1;i<=anstot;i++) printf("2 %d %d\n",ans[i].x, ans[i].y);
}
int t;
int main() {
read(t);
while( t-- ) solve();
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3824kb
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 1 2 1 2 YES 4 2 3 2 2 4 2 2 2 1 2 3 1 YES 4 2 1 2 2 2 3 2 3 4 2 4 5 NO NO
result:
wrong answer you didn't find a solution but jury did (test case 5)