답안 #23065 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
23065	2017-05-02T14:49:19 Z	model_code	Zamjene (COCI16_zamjene)	C++11	126 / 140	6000 ms	145368 KB

zamjene

#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#include <algorithm>

using namespace std;
using llint = long long;

const int MAXN = 1000010;

const int HASH = 1234577;
const int MOD = 1e9 + 7;

int n, q, p[MAXN], r[MAXN], father[MAXN], nodes[MAXN], tot_merges;
llint powb[MAXN], idx[MAXN], val[MAXN], sol;
map<llint, int> diff_nodes;
llint tot_pairs;

void add_nodes(int sgn, llint diff, int m) {
  if (diff != 0) {
    tot_pairs += sgn * m * diff_nodes[-diff];
    // printf("diff = %lld\n",diff);
    // printf("... %d\n",diff_nodes[-diff]);
  }
  diff_nodes[diff] += sgn * m;
}

int dad(int x) {
  if (x == father[x]) return x;
  return father[x] = dad(father[x]);
}

void merge(int u, int v) {
  u = dad(u);
  v = dad(v);
  if (u == v)
    return;
  ++tot_merges;

  add_nodes(-1, idx[u] - val[u], nodes[u]);
  add_nodes(-1, idx[v] - val[v], nodes[v]);
  
  father[v] = u;
  idx[u] += idx[v];
  val[u] += val[v];
  nodes[u] += nodes[v];

  add_nodes(1, idx[u] - val[u], nodes[u]);
}

void add(int sgn, int u, int pos, int value) {
  idx[u] += sgn * powb[pos];
  val[u] += sgn * powb[value];
  nodes[u] += sgn;
}

void init(void) {
  scanf("%d %d",&n,&q);
  
  powb[0] = 1;
  for (int i = 1; i < MAXN; ++i)
    powb[i] = powb[i - 1] * HASH;
  
  for (int i = 1; i <= n; ++i) {
    scanf("%d",&p[i]);
    r[i] = p[i];
    father[i] = i;
    nodes[i] = 1;
  }
  sort(r + 1, r + n + 1);
  
  for (int i = 1; i <= n; ++i) {
    idx[i] = powb[r[i]];
    val[i] = powb[p[i]];
    //printf("%d ---> %d %d\n",i,r[i],p[i]);
    //printf("====== %lld %lld\n",powb[r[i]],powb[p[i]]);
    add_nodes(1, idx[i] - val[i], nodes[i]);
  }
}

int main(void) {
  init();
  while (q-- > 0) {
    int t, a, b;
    scanf("%d",&t);
    if (t == 1) {
      scanf("%d %d",&a,&b);
      int u = dad(a), v = dad(b);
      if (u == v) {
	swap(p[a], p[b]);
	continue;
      }
      
      add_nodes(-1, idx[u] - val[u], nodes[u]);
      add_nodes(-1, idx[v] - val[v], nodes[v]);
      add(-1, dad(a), a, p[a]);
      add(-1, dad(b), b, p[b]);
      
      swap(p[a], p[b]);

      add(1, dad(a), a, p[a]);
      add(1, dad(b), b, p[b]);
      add_nodes(1, idx[u] - val[u], nodes[u]);
      add_nodes(1, idx[v] - val[v], nodes[v]);
    } else if (t == 2) {
      scanf("%d %d",&a,&b);
      merge(a, b);
    } else if (t == 3) {
      printf(diff_nodes[0] == n ? "DA\n" : "NE\n");
    } else {
      printf("%lld\n",tot_pairs);
    }
  }
  
  return 0;
}

Compilation message

zamjene.cpp: In function 'void init()':
zamjene.cpp:59:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n,&q);
                       ^
zamjene.cpp:66:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&p[i]);
                      ^
zamjene.cpp: In function 'int main()':
zamjene.cpp:86:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&t);
                   ^
zamjene.cpp:88:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d",&a,&b);
                           ^
zamjene.cpp:107:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d",&a,&b);
                           ^

Subtask #1
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	41088 KB	Output is correct
2	Correct	3 ms	41088 KB	Output is correct
3	Correct	0 ms	41088 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	41088 KB	Output is correct
2	Correct	6 ms	41088 KB	Output is correct
3	Correct	0 ms	41088 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	41088 KB	Output is correct
2	Correct	6 ms	41088 KB	Output is correct
3	Correct	0 ms	41088 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	41088 KB	Output is correct
2	Correct	0 ms	41088 KB	Output is correct
3	Correct	3 ms	41220 KB	Output is correct

Subtask #5
14.0 / 14.0

#	결과	메모리	Grader output
1	Correct	41088 KB	Output is correct
2	Correct	41088 KB	Output is correct
3	Correct	41220 KB	Output is correct

Subtask #6
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	41220 KB	Output is correct
2	Correct	9 ms	41220 KB	Output is correct
3	Correct	9 ms	41220 KB	Output is correct

Subtask #7
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	73 ms	41220 KB	Output is correct
2	Correct	139 ms	42936 KB	Output is correct
3	Correct	246 ms	46104 KB	Output is correct

Subtask #8
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1756 ms	53892 KB	Output is correct
2	Execution timed out	6000 ms	145368 KB	Execution timed out
3	Halted	0 ms	0 KB	-

Subtask #9
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3246 ms	79500 KB	Output is correct
2	Correct	5766 ms	101016 KB	Output is correct
3	Correct	2316 ms	89136 KB	Output is correct

Subtask #10
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1466 ms	45180 KB	Output is correct
2	Correct	4353 ms	84648 KB	Output is correct
3	Correct	2566 ms	89136 KB	Output is correct