oj.uz

Submission #209140

# Submission time Handle Problem Language Result Execution time Memory
209140 2020-03-13T09:24:02 Z Sensei Zamjene (COCI16_zamjene) C++14
70 / 140
 6000 ms 210624 KB 
/*
	DATE:		2020-03-13 10:51:02
	NAME:		
	PROBLEM:	COCI16_ZAMJENE
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6;

const long long MOD = 1e16 + 3;
const int prime = 331;
const int prime2 = 67;

long long add(long long x, long long y) {
  return ((x % MOD) + (y % MOD)) % MOD;
}

long long sub(long long x, long long y) {
  return ((x % MOD) + MOD - (y % MOD)) % MOD;
}

long long mul(long long x, long long y) {
  return ((x % MOD) * (y % MOD)) % MOD;
}

long long liftt[MAXN + 7];
long long liftt2[MAXN + 7];

long long lift(int x) {
  return liftt[x];
}

long long lift2(int x) {
  return liftt2[x];
}

int p[MAXN + 7];
int q[MAXN + 7];

int par[MAXN + 7];
int r[MAXN + 7];
long long P[MAXN + 7];
long long Q[MAXN + 7];

long long P2[MAXN + 7];
long long Q2[MAXN + 7];

map<pair<long long, long long>, int> cnt;

long long ans_for_4 = 0;

void ins(int x, int y) {
  // cerr << "ins: " << x << " " << y << " " << p[y] << "\n";
  long long t = sub(P[x], Q[x]);
  long long t2 = sub(P2[x], Q2[x]);
  // cerr << t << "\t" << cnt[t] << "\t" << cnt[-t] << "\n";
  if (t != 0 and t2 != 0) {
    ans_for_4 -= r[x] * cnt[{sub(0, t), sub(0, t2)}];
  }
  cnt[{t, t2}] -= r[x];
  
  P[x] = add(P[x], lift(p[y]));
  P2[x] = add(P2[x], lift2(p[y]));

  t = sub(P[x], Q[x]);
  t2 = sub(P2[x], Q2[x]);
  if (t != 0 and t2 != 0) {
    ans_for_4 += r[x] * cnt[{sub(0, t), sub(0, t2)}];
  }
  cnt[{t, t2}] += r[x];
  // cerr << t << "\t" << cnt[t] << "\t" << cnt[-t] << "\n";
}

void del(int x, int y) {
  long long t = sub(P[x], Q[x]);
  long long t2 = sub(P2[x], Q2[x]);
  if (t != 0 and t2 != 0) {
    ans_for_4 -= r[x] * cnt[{sub(0, t), sub(0, t2)}];
  }
  cnt[{t, t2}] -= r[x];
  
  P[x] = sub(P[x], lift(p[y]));
  P2[x] = sub(P2[x], lift2(p[y]));

  t = sub(P[x], Q[x]);
  t2 = sub(P2[x], Q2[x]);

  if (t != 0 and t2 != 0) {
    ans_for_4 += r[x] * cnt[{sub(0, t), sub(0, t2)}];
  }
  cnt[{t, t2}] += r[x];
}

void makeset(int x) {
  par[x] = x;
  r[x] = 1;
  Q[x] = lift(q[x]);
  Q2[x] = lift2(q[x]);
  P[x] = 0;
  P2[x] = 0;
  cnt[{sub(P[x], Q[x]), sub(P2[x], Q2[x])}] += r[x];
  ins(x, x);
}

int findset(int x) {
  if (par[x] != x) {
    par[x] = findset(par[x]);
  }
  return par[x];
}

void link(int x, int y) {
  x = findset(x);
  y = findset(y);
  if (x == y) {
    return;
  }

  if (r[x] > r[y]) {
    par[y] = x;

    long long t = sub(P[x], Q[x]);
    long long t2 = sub(P2[x], Q2[x]);

    if (t != 0 and t2 != 0) {
      ans_for_4 -= r[x] * cnt[{sub(0, t), sub(0, t2)}];
    }
    cnt[{sub(P[x], Q[x]), sub(P2[x], Q2[x])}] -= r[x];

    t = sub(P[y], Q[y]);
    t2 = sub(P2[y], Q2[y]);

    if (t != 0 and t2 != 0) {
      ans_for_4 -= r[y] * cnt[{sub(0, t), sub(0, t2)}];
    }
    cnt[{sub(P[y], Q[y]), sub(P2[y], Q2[y])}] -= r[y];

    P[x] = add(P[x], P[y]);
    P2[x] = add(P2[x], P2[y]);
    Q[x] = add(Q[x], Q[y]);
    Q2[x] = add(Q2[x], Q2[y]);
    r[x] += r[y];

    t = sub(P[x], Q[x]);
    t2 = sub(P2[x], Q2[x]);

    if (t != 0 and t2 != 0) {
      ans_for_4 += r[x] * cnt[{sub(0, t), sub(0, t2)}];
    }
    cnt[{sub(P[x], Q[x]), sub(P2[x], Q2[x])}] += r[x];
  }
  else {
    par[x] = y;

    long long t = sub(P[x], Q[x]);
    long long t2 = sub(P2[x], Q2[x]);

    if (t != 0 and t2 != 0) {
      ans_for_4 -= r[x] * cnt[{sub(0, t), sub(0, t2)}];
    }
    cnt[{sub(P[x], Q[x]), sub(P2[x], Q2[x])}] -= r[x];

    t = sub(P[y], Q[y]);
    t2 = sub(P2[y], Q2[y]);

    if (t != 0 and t2 != 0) {
      ans_for_4 -= r[y] * cnt[{sub(0, t), sub(0, t2)}];
    }
    cnt[{sub(P[y], Q[y]), sub(P2[y], Q2[y])}] -= r[y];

    P[y] = add(P[y], P[x]);
    P2[y] = add(P2[y], P2[x]);
    Q[y] = add(Q[y], Q[x]);
    Q2[y] = add(Q2[y], Q2[x]);
    r[y] += r[x];

    t = sub(P[y], Q[y]);
    t2 = sub(P2[y], Q2[y]);

    if (t != 0 and t2 != 0) {
      ans_for_4 += r[y] * cnt[{sub(0, t), sub(0, t2)}];
    }
    cnt[{sub(P[y], Q[y]), sub(P2[y], Q2[y])}] += r[y];
  }
}

int main() {
  liftt[0] = 1;
  for (int i = 1; i <= MAXN; i++) {
    liftt[i] = mul(liftt[i - 1], prime);
  }

  liftt2[0] = 1;
  for (int i = 1; i <= MAXN; i++) {
    liftt2[i] = mul(liftt2[i - 1], prime2);
  }

  int n, qry;
  cin >> n >> qry;

  for (int i = 1; i <= n; i++) {
    scanf("%d", &p[i]);
    q[i] = p[i];
  }

  sort(q + 1, q + n + 1);

  for (int i = 1; i <= n; i++) {
    makeset(i);
  }

  while (qry--) {
    // for (unordered_map<long long, int>::iterator it = cnt.begin(); it != cnt.end(); it++) {
    //   cerr << it->first << " " << it->second << "\n";
    // }
    int ty;
    scanf("%d", &ty);
    if (ty == 1) {
      int a, b;
      scanf("%d %d", &a, &b);
      int x = findset(a);
      int y = findset(b);
      if (x == y) {
        continue;
      }
      
      del(x, a);
      ins(x, b);
      del(y, b);
      ins(y, a);
      swap(p[a], p[b]);
    }
    else if (ty == 2) {
      int a, b;
      scanf("%d %d", &a, &b);
      link(a, b);
    }
    else if (ty == 3) {
      if (cnt[{0, 0}] == n) {
        printf("DA\n");
      }
      else {
        printf("NE\n");
      }
    }
    else if (ty == 4) {
      printf("%lld\n", ans_for_4);
    }
  }

  return 0;
}

Compilation message

zamjene.cpp: In function 'int main()':
zamjene.cpp:204:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &p[i]);
     ~~~~~^~~~~~~~~~~~~
zamjene.cpp:219:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &ty);
     ~~~~~^~~~~~~~~~~
zamjene.cpp:222:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &a, &b);
       ~~~~~^~~~~~~~~~~~~~~~~
zamjene.cpp:237:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &a, &b);
       ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 16120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 15996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 15992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 16120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16120 KB Output is correct
2 Correct 33 ms 16076 KB Output is correct
3 Correct 32 ms 16120 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 16632 KB Output is correct
2 Correct 40 ms 16632 KB Output is correct
3 Correct 40 ms 16760 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 21240 KB Output is correct
2 Correct 183 ms 23416 KB Output is correct
3 Correct 286 ms 27148 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1924 ms 62396 KB Output is correct
2 Correct 5919 ms 166924 KB Output is correct
3 Execution timed out 6066 ms 210624 KB Time limit exceeded

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3207 ms 114168 KB Output is correct
2 Correct 5056 ms 137908 KB Output is correct
3 Correct 2950 ms 119416 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1616 ms 72600 KB Output is correct
2 Correct 3695 ms 121240 KB Output is correct
3 Correct 2935 ms 119444 KB Output is correct