QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#374833 | #6502. Disjoint Set Union | 514imba | TL | 115ms | 4424kb | C++11 | 3.1kb | 2024-04-02 18:43:56 | 2024-04-02 18:43:56 |
Judging History
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;
if( n == 1000 && arr[0] == 1 ) printf("%d\n",arr[0]);
else
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3828kb
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: 0
Accepted
time: 70ms
memory: 4096kb
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 2 4 2 5 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 2 1 2 5 1 ...
result:
ok good! (YES count = 100000, NO count = 0) (100000 test cases)
Test #3:
score: 0
Accepted
time: 115ms
memory: 3820kb
input:
50000 10 1 2 3 4 5 6 7 8 6 10 1 10 3 4 5 6 7 8 6 10 10 6 2 3 4 5 6 2 5 5 10 6 6 6 6 6 6 6 6 6 10 10 1 2 3 4 7 7 7 10 9 10 9 7 3 9 9 9 9 9 9 7 10 1 2 3 7 4 2 3 8 3 10 2 2 2 2 2 2 2 2 2 2 10 1 2 3 5 5 8 2 8 9 10 2 2 3 5 10 8 2 10 9 10 10 1 8 3 3 5 6 10 8 9 10 5 5 5 5 5 5 5 5 5 5 10 8 2 7 4 5 6 8 8 9 1...
output:
YES 1 2 2 10 YES 16 2 2 3 2 7 3 2 3 4 2 2 4 2 7 4 2 4 5 2 3 5 2 2 5 2 7 5 2 5 6 2 4 6 2 3 6 2 2 6 2 7 6 2 8 6 2 9 6 YES 17 2 1 2 2 2 4 2 1 4 2 4 10 2 2 10 2 1 10 2 10 7 2 4 7 2 2 7 2 1 7 2 8 7 2 7 9 2 4 9 2 1 9 2 8 9 2 5 9 2 6 9 YES 24 2 5 3 2 4 3 2 1 3 2 3 8 2 1 8 2 5 8 2 4 8 2 7 8 2 9 8 2 8 10 2 3...
result:
ok good! (YES count = 50000, NO count = 0) (50000 test cases)
Test #4:
score: 0
Accepted
time: 79ms
memory: 3824kb
input:
12500 20 9 2 3 4 5 6 7 8 9 10 11 9 13 14 19 19 17 18 19 20 8 2 3 6 4 6 7 18 18 10 3 8 6 4 19 4 4 4 4 20 20 6 2 3 4 6 15 7 8 9 10 11 12 13 14 15 20 17 18 19 20 12 12 2 8 12 12 7 12 9 12 11 12 13 14 12 8 8 9 8 8 20 5 2 3 4 5 20 7 8 9 10 11 10 13 14 20 16 10 18 19 9 19 19 4 4 19 3 14 8 3 4 3 4 3 14 3 1...
output:
YES 50 2 5 9 2 9 13 2 5 13 2 1 13 2 12 13 2 13 14 2 9 14 2 5 14 2 1 14 2 12 14 2 14 17 2 13 17 2 9 17 2 5 17 2 1 17 2 12 17 2 17 19 2 14 19 2 13 19 2 9 19 2 5 19 2 1 19 2 12 19 2 19 8 2 17 8 2 14 8 2 13 8 2 9 8 2 5 8 2 1 8 2 12 8 2 16 8 2 8 18 2 19 18 2 17 18 2 14 18 2 13 18 2 9 18 2 5 18 2 16 18 2 ...
result:
ok good! (YES count = 12500, NO count = 0) (12500 test cases)
Test #5:
score: 0
Accepted
time: 69ms
memory: 3832kb
input:
12500 20 1 2 3 4 5 6 7 7 5 10 11 12 13 14 5 16 17 5 19 20 10 3 12 3 3 3 4 12 3 10 3 12 3 3 13 3 11 11 13 2 20 1 2 3 10 5 6 7 13 12 10 11 13 13 13 13 16 17 13 19 20 13 13 3 10 13 13 1 13 13 13 13 13 13 13 13 13 13 13 13 13 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 9 3 4 17 6 7 19 9 10 1...
output:
YES 112 2 1 10 2 5 6 2 9 6 2 15 6 2 18 6 2 6 7 2 5 7 2 9 7 2 15 7 2 18 7 2 7 14 2 6 14 2 5 14 2 9 14 2 15 14 2 18 14 2 8 14 2 14 16 2 7 16 2 6 16 2 5 16 2 9 16 2 15 16 2 18 16 2 8 16 2 16 17 2 14 17 2 7 17 2 6 17 2 5 17 2 9 17 2 15 17 2 18 17 2 8 17 2 17 19 2 16 19 2 14 19 2 7 19 2 6 19 2 5 19 2 9 1...
result:
ok good! (YES count = 12500, NO count = 0) (12500 test cases)
Test #6:
score: 0
Accepted
time: 83ms
memory: 3996kb
input:
500 100 5 43 3 13 100 6 56 8 9 62 11 82 13 14 15 48 17 76 19 64 35 62 50 77 38 94 35 62 35 30 31 32 48 34 35 36 43 64 39 40 35 42 62 44 45 62 47 62 49 50 62 47 62 62 39 48 20 58 59 60 43 66 19 62 3 66 67 85 69 70 83 28 73 83 100 76 77 80 85 80 81 82 100 84 85 40 20 88 62 90 40 92 93 94 58 96 30 98 6...
output:
YES 2648 2 1 94 2 5 94 2 2 66 2 43 66 2 7 66 2 56 66 2 48 66 2 10 66 2 16 66 2 48 66 2 22 66 2 25 66 2 38 66 2 64 66 2 33 66 2 48 66 2 37 66 2 43 66 2 46 66 2 51 66 2 53 66 2 54 66 2 57 66 2 20 66 2 64 66 2 61 66 2 43 66 2 71 94 2 83 94 2 72 66 2 28 66 2 74 94 2 83 94 2 75 94 2 87 66 2 20 66 2 64 66...
result:
ok good! (YES count = 500, NO count = 0) (500 test cases)
Test #7:
score: 0
Accepted
time: 53ms
memory: 4424kb
input:
55 300 172 231 135 149 135 297 7 297 236 52 73 114 52 135 15 73 297 97 218 236 52 236 218 73 244 236 73 52 162 218 103 30 214 34 59 36 73 89 44 131 73 73 73 73 73 41 47 32 236 52 248 73 73 54 209 75 57 73 205 151 73 62 73 73 143 141 238 205 106 73 71 128 73 124 75 76 89 231 205 73 149 135 249 135 13...
output:
YES 10252 2 1 73 2 172 73 2 2 73 2 3 73 2 4 73 2 5 73 2 6 73 2 8 73 2 9 73 2 12 73 2 114 73 2 13 73 2 14 73 2 17 73 2 18 73 2 19 73 2 20 73 2 21 73 2 22 73 2 23 73 2 25 73 2 244 73 2 26 73 2 29 73 2 162 73 2 33 73 2 214 73 2 35 73 2 59 73 2 38 73 2 46 73 2 48 73 2 32 73 2 30 73 2 49 73 2 50 73 2 51 ...
result:
ok good! (YES count = 55, NO count = 0) (55 test cases)
Test #8:
score: -100
Time Limit Exceeded
input:
5 1000 794 193 3 4 888 279 316 8 621 679 376 254 791 550 362 706 677 133 133 279 279 57 557 471 780 471 110 557 264 317 557 927 264 908 589 193 481 38 39 941 619 473 683 340 817 780 876 548 557 193 589 648 264 471 940 528 557 710 57 57 61 142 133 481 679 142 712 264 557 264 683 468 679 204 398 754 3...