fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef long double ld;
  6. typedef pair<ll,ll> pll;
  7. typedef vector<ll> vl;
  8. typedef vector<pll> vpl;
  9. #define pb push_back
  10. #define MAXN 200005
  11. const ll N=32;
  12. #define INF (ll)1e18
  13. #define mod 1000000007
  14. //#define mod 998244353
  15. #define fi first
  16. #define se second
  17. #define mkp make_pair
  18. #define clr(v) v.clear()
  19. #define sze(x) ((ll)x.size())
  20. #define all(v) v.begin(),v.end()
  21. #define endl '\n'
  22. #define level 20
  23. ll timer,cc1,cc;
  24.  
  25. void boost()
  26. {
  27.  ios_base::sync_with_stdio(false);
  28.  cin.tie(NULL);
  29. }
  30.  
  31. ll a[MAXN],deg[MAXN];
  32.  
  33. ll par[MAXN];
  34. set<pll,greater<pll>> ss[MAXN];
  35.  
  36.  
  37. ll fp(ll i)
  38. {
  39.     if(par[par[i]]!=par[i])
  40.     par[i]=fp(par[i]);
  41.  
  42.     return par[i];
  43. }
  44.  
  45. void join(ll a,ll b)
  46. {
  47.     ll j,k;
  48.  
  49.     j=fp(a);
  50.     k=fp(b);
  51.  
  52.     if(j==k)
  53.     return;
  54.  
  55.  
  56.     if(sze(ss[j])>=sze(ss[k]))
  57.     swap(j,k);
  58.  
  59.  
  60.     par[j]=k;
  61.     for(auto x :ss[j])
  62.     {
  63.         ss[k].insert(x);
  64.     }
  65.  
  66.     return;
  67. }
  68.  
  69. int main()
  70. {
  71.  boost();
  72.  
  73.  ll i,t,q,l,r,ans,mid,c=0,j,z,tc,n,k;
  74.  ll h,m,u,mm,w,x,y,l1,r1,d=0,mask,v,mx;
  75.  ld f,f1;
  76.  
  77.  cin>>n>>m;
  78.  vpl g;
  79.  
  80.  for(i=1;i<=n;i++)
  81.  {
  82.  cin>>a[i];
  83.  par[i]=i;
  84.  }
  85.  
  86.  priority_queue<pair<pll,ll>> pq;
  87.  
  88.  for(i=0;i<m;i++)
  89.  {
  90.      cin>>x>>y;
  91.      deg[x]++;
  92.      deg[y]++;
  93.  
  94.      if(fp(x)!=fp(y))
  95.      join(x,y);
  96.  
  97.      else
  98.      c++;
  99.  
  100.  }
  101.  
  102.  l=0;
  103.  for(i=1;i<=n;i++)
  104.  {
  105.      if(deg[i]>a[i])
  106.      {
  107.          c++;
  108.      }
  109.  
  110.      d+=a[i];
  111.      l+=a[i]-deg[i];
  112.  }
  113.  
  114.  z=(d/2);
  115.  q=n-m-1;
  116.  
  117.  if((c>0)||(d&1)||(z!=(n-1))||(l!=(2*q)))
  118.  cout<<-1<<endl;
  119.  
  120.  else
  121.  {
  122.      for(i=1;i<=n;i++)
  123.      {
  124.          l=fp(i);
  125.          z=a[i]-deg[i];
  126.  
  127.          if(z>0)
  128.          ss[l].insert(mkp(z,i));
  129.      }
  130.  
  131.      for(i=1;i<=n;i++)
  132.      {
  133.          if(fp(i)==i)
  134.          {
  135.             if(sze(ss[i])>0)
  136.             {
  137.                 auto p=*ss[i].begin();
  138.                 ss[i].erase(ss[i].begin());
  139.                 pq.push(mkp(p,i));
  140.             }
  141.          }
  142.      }
  143.  
  144.  
  145.      while(q--)
  146.      {
  147.          if(sze(pq)==0)
  148.          {
  149.          c++;
  150.          break;
  151.          }
  152.  
  153.          auto p1=pq.top();
  154.          pq.pop();
  155.  
  156.  
  157.          if(sze(pq)==0)
  158.          {
  159.          c++;
  160.          break;
  161.          }
  162.  
  163.          auto p2=pq.top();
  164.          pq.pop();
  165.  
  166.          l=p1.se;
  167.          r=p2.se;
  168.  
  169.          if(p1.fi.fi-1>0)
  170.          ss[l].insert(mkp(p1.fi.fi-1,p1.fi.se));
  171.  
  172.          if(p2.fi.fi-1>0)
  173.          ss[r].insert(mkp(p2.fi.fi-1,p2.fi.se));
  174.  
  175.          g.pb(mkp(p1.fi.se,p2.fi.se));
  176.  
  177.          join(l,r);
  178.          y=fp(l);
  179.  
  180.          if(sze(ss[y])>0)
  181.          {
  182.              auto p=*ss[y].begin();
  183.              ss[y].erase(ss[y].begin());
  184.              pq.push(mkp(p,y));
  185.          }
  186.  
  187.      }
  188.  
  189.      if(c>0||sze(pq)>0)
  190.      cout<<-1<<endl;
  191.  
  192.      else
  193.      {
  194.          for(auto x :g)
  195.          cout<<x.fi<<" "<<x.se<<endl;
  196.      }
  197.  }
  198.  
  199. return 0;
  200. }
Runtime error #stdin #stdout 0.01s 17320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tiKZSW
language:
C++14 (gcc 8.3)
created:
2 years 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!