fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef pair<int, int> pii;
  6. typedef pair<ll, ll> pll;
  7.  
  8. #define FOR(i, x, y) for (int i = x, _y = y; i <= _y; i++)
  9. #define FOD(i, x, y) for (int i = x, _y = y; i >= _y; i--)
  10. #define em emplace
  11. #define emb emplace_back
  12. #define emf emplace_front
  13. #define fi first
  14. #define se second
  15.  
  16. template<typename T1, typename T2> bool Tmax(T1 &a, const T2 &b) {
  17.     if (a < b) {
  18.         a = b;
  19.         return 1;
  20.     }
  21.     return 0;
  22. }
  23.  
  24. template<typename T1, typename T2> bool Tmin(T1 &a, const T2 &b) {
  25.     if (a > b) {
  26.         a = b;
  27.         return 1;
  28.     }
  29.     return 0;
  30. }
  31.  
  32. const long long INF = (long long) 1e9;
  33. const long long oo = (long long) 1e18;
  34. const long long MOD = (long long) 1e9 + 7;
  35. const char el = '\n';
  36. const int Nmax = 3500 + 7;
  37. const int Mmax = 500 + 7;
  38.  
  39. void File () {
  40.     ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
  41.  
  42.     #define NAME "TEST"
  43.     if (fopen(NAME".inp", "r")) {
  44.         freopen(NAME".inp", "r", stdin);
  45.         freopen(NAME".out", "w", stdout);
  46.     }
  47.  
  48.     #undef NAME
  49.     #define NAME "D:\\Onedrive\\Dokumen\\Code\\TEMPLATE_TEST\\Test"
  50.     if (fopen(NAME".inp", "r")) {
  51.         freopen(NAME".inp", "r", stdin);
  52.         freopen(NAME".out", "w", stdout);
  53.     }
  54. }
  55.  
  56. mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  57. #define rand rd 
  58.  
  59. long long Rand (long long l, long long r) {
  60.     assert(l <= r);
  61.     return l + rd() % (r - l + 1ll);
  62. }
  63.  
  64. int N, T;
  65. int Pos[Nmax];
  66. vector<int> Adj[Nmax];
  67. bitset<Nmax> E[Nmax];
  68. bool VoNghiem[Nmax];
  69.  
  70. signed main () {
  71.     File();
  72.  
  73.     cin >> N >> T;
  74.     FOR(i, 1, N) {
  75.         int u, v; cin >> u >> v;
  76.         Adj[u].emb(v);
  77.         Adj[v].emb(u);
  78.     }
  79.  
  80.     FOR(_, 1, T) {
  81.         FOR(i, 1, N) {
  82.             int x; cin >> x;
  83.             if (!x) E[i].flip(_ + N - 1);
  84.         }
  85.     }
  86.  
  87.     FOR(i, 1, N) {
  88.         E[i].flip(i - 1);
  89.         for (int j : Adj[i]) E[i].flip(j - 1);
  90.     }
  91.  
  92.     FOR(i, 1, N) {
  93.         int FirstPos = -1;
  94.         for (int j = 0; j <= N - 1; j++) {
  95.             if (E[i][j]) {
  96.                 FirstPos = j;
  97.                 break;
  98.             }
  99.         }
  100.  
  101.         if (FirstPos == -1) {
  102.             VoNghiem[i] = 1;
  103.         } 
  104.         else {
  105.             FOR(j, 1, N) {
  106.                 if (i == j) continue;
  107.                 if (E[j][FirstPos]) E[j] ^= E[i];
  108.             }
  109.             Pos[i] = FirstPos;
  110.         }
  111.     }
  112.  
  113.     FOR(j, N, N + T - 1) {
  114.         bool Flag = 0;
  115.         vector<int> Ans;
  116.         Ans.clear();
  117.         FOR(i, 1, N) {
  118.             if (VoNghiem[i] && E[i][j]) {
  119.                 Flag = 1;
  120.                 break;
  121.             }
  122.             if (E[i][j]) Ans.emb(Pos[i] + 1);
  123.         }
  124.         if (Flag) cout << -1 << el;
  125.         else {
  126.             cout << Ans.size() << ' ';
  127.             for (int k : Ans) cout << k << ' ';
  128.             cout << el;
  129.         }
  130.     }
  131.  
  132.  
  133.  
  134.     // vector<int> Ans;
  135.     // Ans.clear();
  136.  
  137.     // FOR(i, 1, N) {
  138.     //     if (E[i][N]) {
  139.     //         FOR(j, 0, N - 1) if (E[i][j]) {
  140.     //             Ans.emb(j + 1);
  141.     //             break;
  142.     //         }
  143.     //     } 
  144.     // }
  145.  
  146.     return 0;
  147. }
  148.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/h06PBb
language:
C++ (gcc 8.3)
created:
74 days 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!