oj.uz

Submission #88315

# Submission time Handle Problem Language Result Execution time Memory
88315 2018-12-05T09:21:15 Z ltomic Zamjena (COCI18_zamjena) C++14
70 / 70
 156 ms 9040 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>

using namespace std;

const int P = 1000, MAXN = 5e4+5;

vector<int> G[MAXN];
vector<int> val;
map <string, int> var;

int n, a[2][MAXN];
int cnt = 0;
char name[20];


bool check(const int &a, const int &b) {
  if (a >= P && b < P) {
    int id = a-P;
    if (val[id] != 0 && val[id] != b) return false;
    val[id] = b;
  }
  return true;
}

int val_comp[MAXN];
int comp[MAXN], cnt_comp;
void dfs(int x) {
  comp[x] = cnt_comp;

  for (int i: G[x]){
    if (comp[i] == cnt_comp) continue;
    if (comp[i] != 0) {
      printf("ERROR\n");
      return;
    }
    dfs(i);
  }
}

bool solve() {
  for (int i = 0; i < n; ++i) {
    int x = a[0][i], y = a[1][i];
    if (x < P && y < P) {
      if (x != y) return false;
      continue;
    }

    if (x == y) continue;
    if (!check(x, y)) return false;
    if (!check(y, x)) return false;
    
    if (x >= P && y >= P) {
      G[x-P].push_back(y-P);
      G[y-P].push_back(x-P);
    }
  }

  for (int i = 0; i < cnt; ++i) {
    if (!comp[i]) {
      ++cnt_comp;
      dfs(i);
    }
  }

  for (int i = 0; i < cnt; ++i) {
    if (val[i] == 0) continue;
    if (val_comp[comp[i]] == 0) {
      val_comp[comp[i]] = val[i];
      continue;
    }
    if (val_comp[comp[i]] != val[i]) {
      return false;
    }
  }

  return true;
}


int main() {
  scanf("%d", &n);
  for (int j = 0; j < 2; ++j) {  
    for (int i = 0; i < n; ++i) {
      if (scanf(" %d", &a[j][i]) == 1) continue;
      scanf(" %s", name);
      if (var.find(std::string(name)) == var.end()) {
        var[std::string(name)] = cnt++;
      }
      a[j][i] = var[std::string(name)]+P;
    }
  }

  val = vector<int>(cnt);

  printf("%s\n", solve() ? "DA" : "NE");
  return 0;
}

Compilation message

zamjena.cpp: In function 'int main()':
zamjena.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
zamjena.cpp:88:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf(" %s", name);
       ~~~~~^~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Correct 3 ms 1656 KB Output is correct
3 Correct 3 ms 1656 KB Output is correct
4 Correct 3 ms 1660 KB Output is correct
5 Correct 4 ms 1764 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1888 KB Output is correct
2 Correct 3 ms 1888 KB Output is correct
3 Correct 4 ms 1888 KB Output is correct
4 Correct 3 ms 1912 KB Output is correct
5 Correct 3 ms 1912 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1912 KB Output is correct
2 Correct 3 ms 1912 KB Output is correct
3 Correct 3 ms 1916 KB Output is correct
4 Correct 3 ms 1920 KB Output is correct
5 Correct 3 ms 1924 KB Output is correct
6 Correct 3 ms 1928 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1932 KB Output is correct
2 Correct 6 ms 1940 KB Output is correct
3 Correct 8 ms 2220 KB Output is correct
4 Correct 9 ms 2372 KB Output is correct
5 Correct 8 ms 2372 KB Output is correct
6 Correct 8 ms 2372 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2980 KB Output is correct
2 Correct 43 ms 3948 KB Output is correct
3 Correct 80 ms 5640 KB Output is correct
4 Correct 91 ms 6148 KB Output is correct
5 Correct 156 ms 9040 KB Output is correct
6 Correct 98 ms 9040 KB Output is correct