Submission #119286

#	Time	Username	Problem	Language	Result	Execution time	Memory
119286		shoemakerjo	Zamjena (COCI18_zamjena)	C++14	70 / 70	115 ms	20600 KiB

zamjena

#include <bits/stdc++.h>

using namespace std;

int n;
const int maxn = 100010;

bool isnum(string& s) {
  for (int i = 0; i < s.length(); i++) {
    if (s[i] - '0' < 0 || s[i]-'0' > 9) return false;
  }
  return true;
}

int nums[maxn*2];
string vs[maxn*2]; //all of these are unioned

map<string, int> lastseen; //lastseen for this string

int par[maxn*2];
set<int> stuff[maxn*2];

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

void unionset(int a, int b) {
  a = findset(a);
  b = findset(b);
  if (a == b) return;
  par[a] = b; //path compression gets lg
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n;
  string cur;
  for (int i = 1; i <= 2*n; i++) {
    par[i] = i;
    cin >> cur;
    if (isnum(cur)) nums[i] = stoi(cur);
    else vs[i] = cur;
  }
  //union me with all else with my string
  for (int i = 1; i <= 2*n; i++) {
    if (nums[i]) continue;
    // cout << i << " :: " << nums[i] << endl;
    if (lastseen.count(vs[i])) {
      // cout << i << " and " << lastseen[vs[i]] << endl;
      unionset(i, lastseen[vs[i]]);
    }
    lastseen[vs[i]] = i;
  }
  for (int i = 1; i <= n; i++) {
    unionset(i, n+i);
  }

  bool ok = true;
  for (int i = 1; i <= 2*n; i++) {
    if (nums[i]) stuff[findset(i)].insert(nums[i]);
  }
  for (int i = 1; i <= 2*n; i++) {
    if (par[i] == i) {
      // cout << i << " : " << stuff[i].size() << endl;
      if (stuff[i].size() > 1) ok = false;
    }
  }
  if (ok) cout << "DA" << endl;
  else cout << "NE" << endl;
}

Compilation message (stderr)

zamjena.cpp: In function 'bool isnum(std::__cxx11::string&)':
zamjena.cpp:9:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.length(); i++) {
                   ~~^~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14