QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#374818 | #6502. Disjoint Set Union | 514imba | TL | 0ms | 0kb | C++11 | 3.0kb | 2024-04-02 18:38:17 | 2024-04-02 18:38:18 |
answer
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=b;i>=a;i--)
#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 rd( 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 retNO { puts("NO"); return; }
#define MAXN 1000
int n;
int f[MAXN+5], g[MAXN+5], frt[MAXN+5], flf[MAXN+5], topovis[MAXN+5];
int fa[2][MAXN+5], in[MAXN+5];
vector<int> cl[MAXN+5], to[MAXN+5];
struct ansNode {
int x, y;
}ans[MAXN*MAXN*2+5];int anstot;
void add( int x , int y ) {
++in[y]; to[x].pb(y);
}
int find( int *fa, int x ) {
if( fa[x] == x ) return x;
return fa[x] = find(fa, fa[x]);
}
void unite( int *fa, int x , int y ) {
x = find(fa,x), y = find(fa,y);
fa[x] = y;
}
queue<int> q; int st[2][MAXN+5];
int arr[MAXN+5];
#define st1 st[x]
#define st2 st[x^1]
bool topo( int rt ) {
while( !q.empty() ) q.pop(); arr[0] = 0;
FOR(i,1,n) if( frt[i] && find(fa[1],i) == rt && !in[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(i,1,n) if( frt[i] && find(fa[1],i) == rt && in[i] ) return false;
int x = 0; st1[0] = st2[0] = 0;
for(auto i: cl[arr[1]]) st1[++st1[0]] = i;
FOR(i,2,arr[0]) {
st2[0] = 0;
ans[++anstot] = {arr[i-1],arr[i]}; if( g[arr[i-1]] != arr[i] ) st2[++st2[0]] = arr[i-1];
FOR(j,1,st1[0]) {
ans[++anstot] = {st1[j],arr[i]};
if( g[st1[j]] != arr[i] ) st2[++st2[0]] = st1[j];
}
for(auto j: cl[arr[i]]) st2[++st2[0]] = j;
x^=1;
}
return true;
}
void solve(){
rd(n); FOR(i,1,n) topovis[i] = false, fa[0][i] = fa[1][i] = i, frt[i] = false, flf[i] = true, cl[i].clear(), to[i].clear(), in[i] = 0; anstot = 0;
FOR(i,1,n) rd(f[i]); FOR(i,1,n) rd(g[i]);
FOR(i,1,n) { if( find(fa[0],i) == find(fa[0],f[i]) && i != f[i] ) retNO unite(fa[0],i,f[i]);} FOR(i,1,n) unite(fa[1],i,g[i]);
FOR(i,1,n) frt[find(fa[0],i)] = true, flf[f[i]] = false;
FOR(i,1,n) if( find(fa[1],i) != find(fa[1],f[i]) ) retNO
FOR(i,1,n) {
if( f[i] != g[i] ) {
if( !frt[g[i]] ) retNO
if( find(fa[0],i) != find(fa[0],g[i]) )add(find(fa[0],i), g[i]);
}
}
FOR(i,1,n) if( flf[i] && !frt[i] ) {
int p=i;
for(bool chg=false;!frt[f[p]];p=f[p]) {
if( chg && f[p] == g[p] ) retNO
if( f[p] != g[p] ) { chg = true, ans[++anstot] = {p,find(fa[0],p)}; if( g[p] != find(fa[0],p) ) cl[find(fa[0],p)].pb(p);}
}
if( f[p] != g[p] ) cl[find(fa[0],p)].pb(p);
}
FOR(i,1,n) if( !topovis[find(fa[1],i)] ) {
if( !topo(find(fa[1],i)) ) retNO
topovis[find(fa[1],i)] = true;
}
puts("YES"); printf("%d\n", anstot);
if( anstot >= 100000 ) return;
FOR(i,1,anstot) printf("2 %d %d\n",ans[i].x,ans[i].y);
return;
}
int main() {
freopen("test.in","r",stdin);
int t; rd(t);
while( t-- ) solve();
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
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