Submission #88315

#	Time	Username	Problem	Language	Result	Execution time	Memory
88315		ltomic	Zamjena (COCI18_zamjena)	C++14	70 / 70	156 ms	9040 KiB

zamjena

#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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14