oj.uz

Submission #119286

# Submission time Handle Problem Language Result Execution time Memory
119286 2019-06-20T23:09:33 Z shoemakerjo Zamjena (COCI18_zamjena) C++14
70 / 70
 115 ms 20600 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16000 KB Output is correct
2 Correct 15 ms 16000 KB Output is correct
3 Correct 15 ms 16000 KB Output is correct
4 Correct 15 ms 16000 KB Output is correct
5 Correct 15 ms 16000 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16000 KB Output is correct
2 Correct 16 ms 16048 KB Output is correct
3 Correct 16 ms 16000 KB Output is correct
4 Correct 16 ms 16000 KB Output is correct
5 Correct 16 ms 16000 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16000 KB Output is correct
2 Correct 15 ms 16000 KB Output is correct
3 Correct 16 ms 16000 KB Output is correct
4 Correct 15 ms 16000 KB Output is correct
5 Correct 15 ms 16000 KB Output is correct
6 Correct 15 ms 16000 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16000 KB Output is correct
2 Correct 16 ms 16000 KB Output is correct
3 Correct 18 ms 16256 KB Output is correct
4 Correct 19 ms 16376 KB Output is correct
5 Correct 20 ms 16256 KB Output is correct
6 Correct 19 ms 16256 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 16640 KB Output is correct
2 Correct 42 ms 17512 KB Output is correct
3 Correct 72 ms 18644 KB Output is correct
4 Correct 85 ms 19192 KB Output is correct
5 Correct 115 ms 20600 KB Output is correct
6 Correct 106 ms 18808 KB Output is correct