B. New Year Permutation

standard solution

hack was

standard solution

#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef vector<int> vi; typedef pair<int, int> pii; #define rep(i,n) for(int (i)=(0);(i)<(n);(i)++) #define rep1(i,n) for(int (i)=(1);(i)<=(n);(i)++) #define fr(i,a,b) for(int (i)=(a);(i)<(b);(i)++) #define mp make_pair #define pb push_back #define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++) #define db(x) cerr << #x << " : " << x << endl; #define pv(c,a,b) cerr << "{ "; fr(i,a,b) cerr<<c[i]<<", "; cerr << "}" << endl; #define fill(a,v) memset(a,v,sizeof(a)) const int inf = (int) 1e9; const int maxn = (int) 1e5 + 10; int n,a[maxn],comp,vis[maxn]; char s[maxn]; vector<int> g[maxn]; void dfs(int x){ vis[x]=comp; rep(i,g[x].size()){ int y=g[x][i]; if(!vis[y]){ dfs(y); } } } int main() { scanf("%d",&n); rep(i,n) scanf("%d",&a[i]); rep(i,n){ scanf("%s",s); rep(j,n){ if(s[j]=='1'){ g[i].pb(j); } } } comp=1; rep(i,n) if(!vis[i]){ dfs(i); comp++; } rep(i,n) fr(j,i+1,n) if(vis[i]==vis[j] && a[i]>a[j]) swap(a[i],a[j]); rep(i,n) { if(i+1!=n)printf("%d ",a[i]); else printf("%d\n",a[i]); } return 0; }

__my mistake____most imp point its not just the connected nodes where exchanges can be made but which node belong to the same tree there exchanges can be made , like in graph A-B-C so exchange can of course be made bet A and B , B- C but a direct exchange can also be made bet A-C. .something similar to floyd warshall , but yes dat cannot be applies because different forests exist in the graph.__

hack was

3 3 1 2 001 001 110

my output was 2 1 3 bcz if we dont consider that above situation we would never be able to perform a exchange between 1st and 2nd (positions) so the value 1 will never come to 1st place

but if we look at the above solution a exchange can be made bcz 1st and position belong to same forest via 3rd position