Submission #1454535


Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int N;
int V;
int A[100001], B[100001];
int K;
int U[100001], R[100001];
vector<int> G[100001];

int find(int x) {
  if (U[x] == x) return x;
  return U[x] = find(U[x]);
}

void unite(int x, int y) {
  x = find(x), y = find(y);
  if (x == y) return;
  if (R[x] < R[y]) swap(x, y);
  U[y] = x;
  R[x] += R[y];
  R[y] = 0;
  K--;
}

bool same(int x, int y) {
  return find(x) == find(y);
}

void add_edge(int x, int y) {
  G[x].pb(y);
  G[y].pb(x);
  unite(x, y);
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N;
  int g = 0;
  rep(i, N) {
    cin >> A[i];
    g ^= A[i];
  }
  A[N] = g;

  g = 0;
  rep(i, N) {
    cin >> B[i];
    g ^= B[i];
  }
  B[N] = g;

  vector<int> as, bs;
  rep(i, N+1) {
    as.pb(A[i]);
    bs.pb(B[i]);
  }
  sort(all(as));
  sort(all(bs));
  if (as != bs) {
    cout << -1 << "\n";
    return 0;
  }
  rep(i, N+1) assert(as[i] == bs[i]);
  uniq(as);
  V = as.size();
  rep(i, N+1) {
    A[i] = lower_bound(all(as), A[i]) - as.begin();
    B[i] = lower_bound(all(as), B[i]) - as.begin();
  }
  //rep(i, N+1) cout<<A[i]<<","; cout<<"\n";
  //rep(i, N+1) cout<<B[i]<<","; cout<<"\n";
  K = V;
  rep(i, V) U[i] = i, R[i] = 1;

  int edges = 0;
  rep(i, N) {
    if (A[i] == B[i]) continue;
    add_edge(A[i], B[i]);
    edges++;
  }
  rep(i, V) if (G[i].empty()) K--;

  int s = B[N], t = A[N];
  assert(same(s, t));
  if (G[s].empty()) K++;
  assert(K > 0);

  cout << edges+K-1 << "\n";
  return 0;
}

Submission Info

Submission Time
Task D - XOR Replace
User funcsr
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 2065 Byte
Status AC
Exec Time 75 ms
Memory 8052 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 4
AC × 74
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt, 1_56.txt, 1_57.txt, 1_58.txt, 1_59.txt, 1_60.txt, 1_61.txt, 1_62.txt, 1_63.txt, 1_64.txt, 1_65.txt, 1_66.txt, 1_67.txt, 1_68.txt, 1_69.txt
Case Name Status Exec Time Memory
0_00.txt AC 2 ms 2560 KB
0_01.txt AC 2 ms 2560 KB
0_02.txt AC 2 ms 2560 KB
0_03.txt AC 2 ms 2560 KB
1_00.txt AC 2 ms 2560 KB
1_01.txt AC 2 ms 2560 KB
1_02.txt AC 2 ms 2560 KB
1_03.txt AC 2 ms 2560 KB
1_04.txt AC 2 ms 2560 KB
1_05.txt AC 2 ms 2560 KB
1_06.txt AC 2 ms 2560 KB
1_07.txt AC 43 ms 5108 KB
1_08.txt AC 53 ms 8052 KB
1_09.txt AC 47 ms 8052 KB
1_10.txt AC 25 ms 4980 KB
1_11.txt AC 23 ms 4348 KB
1_12.txt AC 26 ms 4980 KB
1_13.txt AC 26 ms 4852 KB
1_14.txt AC 32 ms 5236 KB
1_15.txt AC 27 ms 4348 KB
1_16.txt AC 31 ms 5236 KB
1_17.txt AC 26 ms 4348 KB
1_18.txt AC 35 ms 5236 KB
1_19.txt AC 28 ms 4348 KB
1_20.txt AC 35 ms 5236 KB
1_21.txt AC 29 ms 4348 KB
1_22.txt AC 39 ms 5236 KB
1_23.txt AC 30 ms 4348 KB
1_24.txt AC 41 ms 5236 KB
1_25.txt AC 30 ms 4348 KB
1_26.txt AC 43 ms 5236 KB
1_27.txt AC 31 ms 4348 KB
1_28.txt AC 44 ms 5364 KB
1_29.txt AC 31 ms 4348 KB
1_30.txt AC 48 ms 5364 KB
1_31.txt AC 32 ms 4348 KB
1_32.txt AC 49 ms 5364 KB
1_33.txt AC 33 ms 4348 KB
1_34.txt AC 54 ms 5620 KB
1_35.txt AC 34 ms 4348 KB
1_36.txt AC 54 ms 5492 KB
1_37.txt AC 34 ms 4348 KB
1_38.txt AC 64 ms 6132 KB
1_39.txt AC 35 ms 4348 KB
1_40.txt AC 64 ms 6132 KB
1_41.txt AC 35 ms 4348 KB
1_42.txt AC 70 ms 6900 KB
1_43.txt AC 35 ms 4348 KB
1_44.txt AC 71 ms 7028 KB
1_45.txt AC 35 ms 4348 KB
1_46.txt AC 74 ms 7668 KB
1_47.txt AC 34 ms 4348 KB
1_48.txt AC 74 ms 7796 KB
1_49.txt AC 35 ms 4348 KB
1_50.txt AC 74 ms 7924 KB
1_51.txt AC 34 ms 4348 KB
1_52.txt AC 74 ms 7924 KB
1_53.txt AC 35 ms 4348 KB
1_54.txt AC 74 ms 8052 KB
1_55.txt AC 34 ms 4348 KB
1_56.txt AC 74 ms 8052 KB
1_57.txt AC 36 ms 4348 KB
1_58.txt AC 74 ms 8052 KB
1_59.txt AC 35 ms 4348 KB
1_60.txt AC 74 ms 8052 KB
1_61.txt AC 35 ms 4348 KB
1_62.txt AC 75 ms 8052 KB
1_63.txt AC 33 ms 4348 KB
1_64.txt AC 74 ms 8052 KB
1_65.txt AC 34 ms 4348 KB
1_66.txt AC 73 ms 8052 KB
1_67.txt AC 34 ms 4348 KB
1_68.txt AC 74 ms 8052 KB
1_69.txt AC 35 ms 4348 KB