Submission #34364426

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

const int maxN = 200011;

int n, m, a[maxN], b[maxN];
vector< pair<int, int> > adj[maxN];
int sol[maxN];
bool us[maxN];

void dfs(int node) {
  us[node] = true;
  //cerr << "!" << node << '\n';

  for (auto to: adj[node]) {
    int other = to.first;
    int kind = to.second < 0 ? -1 : 1;
    int pos = to.second * kind;
    //cerr << other << ' ' << kind << ' ' << pos << '\n';

    if (sol[pos] == 0) sol[pos] = kind;
    //cerr << sol[pos] << '\n';
    if (!us[other]) dfs(other);
  }
}

int main()
{
  cin >> n >> m;
  for (int i = 1; i <= m; i++) cin >> a[i];
  for (int i = 1; i <= m; i++) cin >> b[i];

  for (int i = 1; i <= m; i++) {
    adj[a[i]].pb(mp(b[i], i));
    adj[b[i]].pb(mp(a[i], -i));
  }

  for (int i = 1; i <= n; i++)
    if (!us[i])
      dfs(i);

  for (int i = 1; i <= m; i++) { 
    //cerr << sol[i];
    cout << (sol[i] > 0 ? 0 : 1);
  }




  return 0;
}

Submission Info

Judge Result