fork download
copy 
  1.  
  2. #include<bits/stdc++.h>
  3. #define inf 0x3f3f3f3f
  4. #define LL long long
  5. #define FastRead ios_base::sync_with_stdio(0);cin.tie(0);
  6. #define pii pair<int,int>
  7. using namespace std;
  8.  
  9. struct edge
  10. {
  11.     int u,v,w;
  12.     bool operator<(const edge& p) const
  13.     {
  14.         return w < p.w;
  15.     }
  16. };
  17. int par[505];
  18. int vis[505];
  19. int co[505];
  20. vector<edge>e;
  21. vector<int>tree[505];
  22. map< pair<int,int> ,int >mp;
  23. int find(int n)
  24. {
  25.     if(n==par[n])return n;
  26.     return par[n]=find(par[n]);
  27. }
  28.  
  29. int mst(int n)
  30. {
  31.     sort(e.begin(),e.end());
  32.     int i,s=0,cnt=0,u,v;
  33.     for(i=0;i<=n;i++)par[i]=i;
  34.     for(i=0;i<e.size();i++)
  35.     {
  36.         u=find(e[i].u);
  37.         v=find(e[i].v);
  38.         if(u!=v)
  39.         {
  40.             par[u]=v;
  41.             cnt++;
  42.             tree[u].push_back(v);
  43.             tree[v].push_back(u);
  44.             if(u<v)swap(u,v);
  45.             mp[make_pair(u,v)]=e[i].w;
  46.             if(cnt==n-1)break;
  47.         }
  48.     }
  49. }
  50. int dfs(int node,int cost)
  51. {
  52.     vis[node]=1;
  53.  
  54.     int i,a,b,c;
  55.     for(i=0;i<tree[node].size();i++)
  56.     {
  57.         a=tree[node][i];
  58.         b=a;
  59.         c=node;
  60.         if(b<c)swap(b,c);
  61.         pii x=make_pair(b,c);
  62.         if(vis[a]==0)
  63.         {
  64.             co[a]=max(cost,mp[x]);
  65.             dfs(a,co[a]);
  66.         }
  67.     }
  68. }
  69.  
  70. int main()
  71. {
  72.     FastRead
  73.     int test,cs=0;
  74.     cin>>test;
  75.     while(test--)
  76.     {
  77.         memset(vis,0,sizeof(vis));
  78.         memset(co,0,sizeof(co));
  79.         memset(par,0,sizeof(par));
  80.         mp.clear();
  81.  
  82.         int n,m,i,u,v,w,t;
  83.         for(i=0;i<505;i++)tree[i].clear();
  84.         e.clear();
  85.  
  86.         cin>>n>>m;
  87.         edge get;
  88.         for(i=0;i<m;i++)
  89.         {
  90.             cin>>get.u>>get.v>>get.w;
  91.             e.push_back(get);
  92.  
  93.         }
  94.         cin>>t;
  95.         mst(n);
  96.         dfs(t,0);
  97.         cout<<"Case "<<++cs<<":\n";
  98.         for(i=0;i<n;i++)
  99.         {
  100.             if(i==t)cout<<"0\n";
  101.             else if(co[i]==0)cout<<"Impossible\n";
  102.             else cout<<co[i]<<"\n";
  103.         }
  104.     }
  105. }
  106.  
Runtime error #stdin #stdout #stderr 2.58s 791040KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/c5CFdl
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

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!