fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //Uzumaki Naruto :)
  5. #define TRACE
  6.  
  7. #ifdef TRACE
  8. #define dbgA(a,n)    for(int i = 0; i < n; ++i) cerr << a[i] << " ";cerr << endl;
  9. #define dbg(args...) {debug,args; cerr<<endl;}
  10. #define pause()      cin.get();cin.get();
  11.  
  12. #else
  13. #define dbgA(a,n)
  14. #define dbg(args...)
  15. #define pause()
  16.  
  17. #endif
  18.  
  19. struct debugger {
  20.     template<typename T> debugger& operator , (const T& v) {
  21.         cerr<<v<<" "; return *this;
  22.     }
  23. } debug;
  24.  
  25. template <typename T1, typename T2>
  26. inline ostream& operator << (ostream& os, const pair<T1, T2>& p) {
  27.     return os << "(" << p.first << ", " << p.second << ")";
  28. }
  29.  
  30. template<typename T>
  31. inline ostream &operator << (ostream & os,const vector<T>& v) {
  32.     bool first = true; os << "[";
  33.     for (typename vector<T>::const_iterator ii = v.begin(); ii != v.end(); ++ii) {
  34.         if(!first) os << ", ";
  35.         os << *ii; first = false;
  36.     }
  37.     return os << "]";
  38. }
  39.  
  40. typedef long long LL;
  41. typedef pair<int,int> pii;
  42. typedef vector<int> vi;
  43.  
  44. const int NN = 112345;
  45.  
  46. vector<int> g[NN],v[NN];
  47. int ans[5*NN],p[NN],x[NN];
  48. int N,M,tot = 0, cnt = 0;
  49. bool vis[NN];
  50.  
  51. void build(int st){
  52.     if (!tot) return;
  53.     vis[st] = true;
  54.     tot -= p[st];
  55.  
  56.     int sz = g[st].size();
  57.     for(int i = 0; i < sz; ++i){
  58.         int nw = g[st][i];
  59.         if (tot and !vis[nw]){
  60.             v[st].push_back(nw);
  61.             v[nw].push_back(st);
  62.             build(nw);
  63.         }
  64.     }
  65. }
  66.  
  67. void path(int st,int pa,int b){
  68.     vis[st] = true;
  69.     x[st] ^= 1;
  70.     ans[cnt++] = st;
  71.  
  72.     int sz = v[st].size();
  73.     if (!sz and (x[st]^p[st])){
  74.         ans[cnt++] = pa;
  75.         ans[cnt++] = st;
  76.         x[st] ^= 1;
  77.         x[pa] ^= 1;
  78.     }
  79.  
  80.     for(int i = 0; i < sz; ++i){
  81.         int nw = v[st][i];
  82.         if (vis[nw]) continue;
  83.         path(nw,st,i+1);
  84.     }
  85.  
  86.     if (pa != -1 and b < v[pa].size())
  87.         ans[cnt++] = pa, x[pa] ^= 1;
  88.     else if (pa != -1 and (x[pa]^p[pa]))
  89.         ans[cnt++] = pa, x[pa] ^= 1;
  90. }
  91.  
  92. void solve(){
  93.     cin >> N >> M;
  94.     for(int i = 0; i < M; ++i){
  95.         int a,b;
  96.         cin >> a >> b;
  97.         g[a].push_back(b);
  98.         g[b].push_back(a);
  99.     }
  100.  
  101.     for(int i = 1; i <= N; ++i)
  102.         cin >> p[i], tot += p[i];
  103.     int st = -1;
  104.     for(int i = 1; i <= N; ++i) if (p[i]){
  105.         st = i;
  106.         break;
  107.     }
  108.  
  109.     //dbg(st);
  110.     build(st);
  111.     if (tot){
  112.         cout << "-1\n";
  113.         return;
  114.     }
  115.  
  116.     memset(vis,false,sizeof(vis));
  117.     if (st != -1) path(st,-1,-1);
  118.     assert(cnt <= 4*N);
  119.  
  120.     cout << cnt << endl;
  121.     for(int i = 0; i < cnt; ++i){
  122.         cout << ans[i];
  123.         if (i+1 < cnt) cout << " ";
  124.         else cout << endl;
  125.     }
  126. }
  127.  
  128. int main()
  129. {
  130.     //ios_base::sync_with_stdio(0);
  131.     //cin.tie(NULL);
  132.     solve();
  133.     return 0;
  134. }
  135.  
Success #stdin #stdout 0s 9248KB
comments (?)
stdin
copy 
10 10
2 1
2 3
4 2
4 5
3 6
5 7
8 4
4 9
5 10
4 7
0 0 1 0 1 1 1 0 1 0
stdout
copy 
18
3 2 1 2 4 5 7 5 10 5 4 8 4 9 4 3 6 3
https://ideone.com/EWR4KA
language:
C++14 (gcc 8.3)
created:
9 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!