QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#373648 | #6502. Disjoint Set Union | 514imba | WA | 73ms | 3836kb | C++11 | 2.9kb | 2024-04-01 21:22:36 | 2024-04-01 21:22: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( find(i) != find(g[i]) ) add(find(i),g[i]);
unite(i,g[i],1);
}
for(int i=1;i<=n;i++)
if( f[i] != g[i] && !frt[g[i]] ) { puts("NO"); return; }
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3836kb
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 YES 7 2 6 2 2 2 5 2 3 5 2 5 4 2 2 4 2 4 1 2 2 1
result:
ok good! (YES count = 4, NO count = 1) (5 test cases)
Test #2:
score: -100
Wrong Answer
time: 73ms
memory: 3820kb
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 2 2 1 2 2 5 2 YES 0 YES 6 2 2 3 2 3 4 2 5 4 2 2 4 2 4 1 2 5 1 YES 2 2 3 2 2 5 2 YES 0 YES 2 2 1 5 2 2 3 YES 4 2 3 1 2 2 5 2 5 4 2 2 4 YES 1 2 5 2 YES 1 2 2 3 YES 3 2 1 2 2 3 4 2 5 4 YES 1 2 1 5 YES 5 2 1 4 2 3 4 2 4 5 2 1 5 2 3 5 YES 4 2 3 4 2 4 5 2 3 5 2 5 1 YES 5 2 4 3 2 2 3 2 3 1 2 5 1 2 2 1 ...
result:
wrong answer f[3] = 5, but expected 1 (test case 247)