fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int ll;
  5. typedef unsigned long long int ull;
  6. #define IOS ios_base::sync_with_stdio(0);  cin.tie(0); cout.tie(0);
  7.  
  8. typedef pair<int,int>pr;
  9. #define mp   make_pair
  10. #define all(i)     i.begin() , i.end()
  11. #define ft     first
  12. #define sn     second
  13. #define pb push_back
  14. #define eps 1e-9
  15. #define SP cout<<fixed<<setprecision(10);
  16.  
  17. #define inf 100000
  18. #define MAXN 1010
  19.  
  20. const int mod = 1e9+7;
  21.  
  22. #define dbg cout<<"rony\n";
  23. #define en "\n"
  24.  
  25. vector<int>g[MAXN];
  26. int vis[MAXN];
  27. int a[MAXN];
  28. vector<int>ind,val;
  29.  
  30. void dfs(int nd)
  31. {
  32.     vis[nd]  = 1;
  33.     ind.pb(nd);
  34.     val.pb(a[nd]);
  35.  
  36.     for(auto i:g[nd])
  37.     {
  38.         if(vis[i] == 1) continue;
  39.         dfs(i);
  40.     }
  41. }
  42. void solve()
  43. {
  44.   int n,m;
  45.   cin >> n >> m;
  46.  
  47.   for(int i = 1;i <= n;i++) cin >> a[i];
  48.  
  49.   for(int i = 1;i <= m;i++)
  50.   {
  51.      int x,y;
  52.      cin >> x >> y;
  53.      g[x].pb(y);
  54.      g[y].pb(x);
  55.   }
  56.  
  57.   for(int i = 1;i <= n;i++)
  58.   {
  59.     if(vis[i] == 0)
  60.     {
  61.         ind.clear();
  62.         val.clear();
  63.         dfs(i);
  64.         sort(all(ind));
  65.         sort(all(val));
  66.         for(int j = 0;j < ind.size();j++)
  67.         {
  68.             a[ind[j]] = val[j];
  69.         }
  70.     }
  71.   }
  72.  
  73.   for(int i = 1;i <= n;i++)
  74.      cout<<a[i]<<" ";
  75.  cout<<en;
  76.  
  77.    for(int i = 1;i <= n;i++)
  78.    {
  79.      g[i].clear();
  80.      vis[i] = 0;
  81.    }
  82. }
  83.  
  84. int main()
  85. {
  86.     IOS;
  87.     int t;
  88.   cin >> t;
  89.   //t = 1;
  90.     while ( t-- )
  91.     {
  92.  
  93.         solve();
  94.     }
  95.     return 0;
  96. }
  97.  
Time limit exceeded #stdin #stdout 5s 1577168KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy
https://ideone.com/iovpUi
problem IITKWPCI, based on SPOJ submission 30094458 (CPP14), 2022-09-25 15:33:02
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!