fork download 
  1. #include<bits/stdc++.h>
  2. #define arrsize 300001
  3. #define dpsize 1001
  4. #define vpp vector<PP>
  5. #define vll vector<ll>
  6. #define vcc vector<char>
  7. #define endl "\n"
  8. #define vbb vector<bool>
  9. #define w(t) while(t--)
  10. #define PP pair<ll,ll>
  11. #define test(x) ll t; cin>>t; w(t) x()
  12. #define __lb lower_bound
  13. #define __ub upper_bound
  14. #define szs(x) x.length()
  15. #define szv(x) x.size()*1ll
  16. #define INF 1999999996000000010
  17. #define ll long long int
  18. #define takeINP(arr,n) for(long long int i=0;i<n;i++) cin>>arr[i];
  19. #define f(i,s,e) for(long long int i=s;i<e;i++)
  20. #define cf(i,s,e) for(long long int i=s;i<=e;i++)
  21. #define rf(i,e,s) for(long long int i=e-1;i>=s;i--)
  22. #define mem(arr) memset(arr,0,sizeof(arr));
  23. #define MOD 1000000007
  24. #define rsz(x,n) x.resize(n)
  25. #define cbit(x) __builtin_popcount(x)
  26. #define rsr(x,n) x.reserve(n)
  27. #define mp(a,b) make_pair(a,b)
  28. #define float long  double
  29. #define pb push_back
  30. #define print(arr,s,e) f(i,s,e) cout<<arr[i]<<" "; cout<<endl;
  31. #define all(v) v.begin(),v.end()
  32. #define ff first
  33. #define ss second
  34. #define vll vector<ll>
  35. #define triplet pair<ll,pair<ll,ll> >
  36. #define MITR(a,b) map<a,b>::reverse_iterator
  37. using namespace std;
  38. using namespace chrono;
  39. bool rcomp(PP a,PP b){
  40.     return a>b;
  41. }
  42.  
  43. ll cost[arrsize];
  44. vll edges[arrsize];
  45. ll deg[arrsize] = {};
  46.  
  47. void dfs(ll src, vll &visited, ll col) {
  48.     visited[src] = col;
  49.     for (auto itr : edges[src]) {
  50.         if (visited[itr] != -1) continue;
  51.         dfs(itr, visited, col);
  52.     }
  53. }
  54.  
  55. void solve() {
  56.     bool cant = false;
  57.     ll n, m; cin >> n >> m;
  58.     f(i, 0, n) cin >> cost[i];
  59.     cf(i, 1, m) {
  60.         ll x, y; cin >> x >> y;
  61.         x--; y--;
  62.         edges[x].push_back(y);
  63.         edges[y].push_back(x);
  64.         deg[x]++; deg[y]++;
  65.         if (deg[x] > cost[x] or deg[y] > cost[y]) {
  66.             cant = true;
  67.         }
  68.     }
  69.     if (cant) {
  70.         cout << "-1" << endl;
  71.         return;
  72.     }
  73.     vll visited(n, -1);
  74.     ll col = 0;
  75.     f(i, 0, n) {
  76.         if (visited[i] != -1) continue;
  77.         dfs(i, visited, col);
  78.         col++;
  79.     }
  80.     vector<vpp> grps(col);
  81.     f(i, 0, n) {
  82.         if (deg[i] != cost[i]) grps[visited[i]].push_back({cost[i] - deg[i], i});
  83.     }
  84.  
  85.     set<PP> s;
  86.     ll sum = 0;
  87.     f(i, 0, col) {
  88.         sort(all(grps[i]), rcomp);
  89.         if (grps[i].size() < 1) {
  90.             cant = true;
  91.             break;
  92.         }
  93.         else {
  94.             for (auto itr : grps[i]) sum += (itr.ff);
  95.             s.insert(grps[i].back());
  96.             grps[i].pop_back();
  97.         }
  98.     }
  99.     cant = cant or sum != 2 * (n - m - 1);
  100.     if (cant) {
  101.         cout << "-1" << endl;
  102.         return;
  103.     }
  104.     vpp ret;
  105.     while (s.size() > 1) {
  106.         // for (auto elem : s) cout << elem.ff << " " << elem.ss << endl;
  107.         // cout << "------" << endl;
  108.         auto elem1 = *s.begin();
  109.         s.erase(s.begin());
  110.         auto elem2 = *s.rbegin();
  111.         s.erase(elem2);
  112.         elem1.ff--; elem2.ff--;
  113.         ret.push_back({elem1.ss, elem2.ss});
  114.  
  115.         if (elem1.ff != 0) {
  116.             cout << "-1" << endl;
  117.             return;
  118.         }
  119.         else if (grps[visited[elem1.ss]].size()) {
  120.             s.insert(grps[visited[elem1.ss]].back());
  121.             grps[visited[elem1.ss]].pop_back();
  122.         }
  123.  
  124.         if (elem2.ff != 0) s.insert(elem2);
  125.         else{
  126.             if (grps[visited[elem2.ss]].size()) {
  127.                 s.insert(grps[visited[elem2.ss]].back());
  128.                 grps[visited[elem2.ss]].pop_back();
  129.             }
  130.         }
  131.     }
  132.     if (s.size()) {
  133.         cout << "-1" << endl;
  134.         return;
  135.     }
  136.     for (auto itr : ret) cout << itr.ff + 1 << " " << itr.ss + 1 << endl;
  137. }
  138.  
  139. int main() {
  140.     ios_base::sync_with_stdio(false);
  141.     cin.tie(NULL);
  142.     solve();
  143. }
Success #stdin #stdout 0.01s 13744KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
https://ideone.com/BjHtrF
#include<bits/stdc++.h>
#define arrsize 300001
#define dpsize 1001
#define vpp vector<PP>
#define vll vector<ll>
#define vcc vector<char>
#define endl "\n"
#define vbb vector<bool>
#define w(t) while(t--)
#define PP pair<ll,ll>
#define test(x) ll t; cin>>t; w(t) x()
#define __lb lower_bound
#define __ub upper_bound
#define szs(x) x.length()
#define szv(x) x.size()*1ll
#define INF 1999999996000000010
#define ll long long int
#define takeINP(arr,n) for(long long int i=0;i<n;i++) cin>>arr[i];
#define f(i,s,e) for(long long int i=s;i<e;i++)
#define cf(i,s,e) for(long long int i=s;i<=e;i++)
#define rf(i,e,s) for(long long int i=e-1;i>=s;i--)
#define mem(arr) memset(arr,0,sizeof(arr));
#define MOD 1000000007
#define rsz(x,n) x.resize(n)
#define cbit(x) __builtin_popcount(x)
#define rsr(x,n) x.reserve(n)
#define mp(a,b) make_pair(a,b)
#define float long double
#define pb push_back
#define print(arr,s,e) f(i,s,e) cout<<arr[i]<<" "; cout<<endl;
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define vll vector<ll>
#define triplet pair<ll,pair<ll,ll> >
#define MITR(a,b) map<a,b>::reverse_iterator
using namespace std;
using namespace chrono;
bool rcomp(PP a,PP b){
return a>b;
}

ll cost[arrsize];
vll edges[arrsize];
ll deg[arrsize] = {};

void dfs(ll src, vll &visited, ll col) {
visited[src] = col;
for (auto itr : edges[src]) {
if (visited[itr] != -1) continue;
dfs(itr, visited, col);
}
}

void solve() {
bool cant = false;
ll n, m; cin >> n >> m;
f(i, 0, n) cin >> cost[i];
cf(i, 1, m) {
ll x, y; cin >> x >> y;
x--; y--;
edges[x].push_back(y);
edges[y].push_back(x);
deg[x]++; deg[y]++;
if (deg[x] > cost[x] or deg[y] > cost[y]) {
cant = true;
}
}
if (cant) {
cout << "-1" << endl;
return;
}
vll visited(n, -1);
ll col = 0;
f(i, 0, n) {
if (visited[i] != -1) continue;
dfs(i, visited, col);
col++;
}
vector<vpp> grps(col);
f(i, 0, n) {
if (deg[i] != cost[i]) grps[visited[i]].push_back({cost[i] - deg[i], i});
}

set<PP> s;
ll sum = 0;
f(i, 0, col) {
sort(all(grps[i]), rcomp);
if (grps[i].size() < 1) {
cant = true;
break;
}
else {
for (auto itr : grps[i]) sum += (itr.ff);
s.insert(grps[i].back());
grps[i].pop_back();
}
}
cant = cant or sum != 2 * (n - m - 1);
if (cant) {
cout << "-1" << endl;
return;
}
vpp ret;
while (s.size() > 1) {
// for (auto elem : s) cout << elem.ff << " " << elem.ss << endl;
// cout << "------" << endl;
auto elem1 = *s.begin();
s.erase(s.begin());
auto elem2 = *s.rbegin();
s.erase(elem2);
elem1.ff--; elem2.ff--;
ret.push_back({elem1.ss, elem2.ss});

if (elem1.ff != 0) {
cout << "-1" << endl;
return;
}
else if (grps[visited[elem1.ss]].size()) {
s.insert(grps[visited[elem1.ss]].back());
grps[visited[elem1.ss]].pop_back();
}

if (elem2.ff != 0) s.insert(elem2);
else{
if (grps[visited[elem2.ss]].size()) {
s.insert(grps[visited[elem2.ss]].back());
grps[visited[elem2.ss]].pop_back();
}
}
}
if (s.size()) {
cout << "-1" << endl;
return;
}
for (auto itr : ret) cout << itr.ff + 1 << " " << itr.ss + 1 << endl;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
language:
C++14 (gcc 8.3)
created:
4 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!