oj.uz

Submission #100383

# Submission time Handle Problem Language Result Execution time Memory
100383 2019-03-10T19:48:54 Z cvele Zamjena (COCI18_zamjena) C++14
70 / 70
 158 ms 11128 KB 
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>

using namespace std;

const int N = 100005;

int n;
string a[N], b[N];
int cnt = 1;
int p[N];
int what[N];
map <string, int> id;

int fs(int u) {
  return (p[u] == u ? u : p[u] = fs(p[u]));
}

void join(int x, int y) {
  int aa = fs(x), bb = fs(y);
  if (aa == bb) return;
  if (what[aa] && what[bb] && (what[aa] != what[bb])) {
    cout << "NE" << endl;
    exit(0);
  }
  if (!what[aa]) {
    p[aa] = bb;
  } else {
    p[bb] = aa;
  }
}

int tonum(string a) {
  int ans = 0;
  for (int i = 0; i < a.size(); i++) {
    ans = ans * 10 + (a[i] - '0');
  }
  return ans;
}

int main() {
  cin >> n;
  for (int i = 0; i < N; i++) p[i] = i;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (!id[a[i]]) {
      id[a[i]] = cnt++;
    }
    if (isdigit(a[i][0])) {
      what[id[a[i]]] = tonum(a[i]);
    }
  }
  for (int i = 0; i < n; i++) {
    cin >> b[i];
    if (!id[b[i]]) {
      id[b[i]] = cnt++;
    }
    if (isdigit(b[i][0])) {
      what[id[b[i]]] = tonum(b[i]);
    }
  }
  for (int i = 0; i < n; i++) {
    join(id[a[i]], id[b[i]]);
  }
  cout << "DA" << endl;
  return 0;
}

Compilation message

zamjena.cpp: In function 'int tonum(std::__cxx11::string)':
zamjena.cpp:50:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size(); i++) {
                   ~~^~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7040 KB Output is correct
2 Correct 9 ms 7040 KB Output is correct
3 Correct 8 ms 6912 KB Output is correct
4 Correct 8 ms 6912 KB Output is correct
5 Correct 7 ms 6912 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6912 KB Output is correct
2 Correct 8 ms 6912 KB Output is correct
3 Correct 9 ms 6964 KB Output is correct
4 Correct 8 ms 6912 KB Output is correct
5 Correct 7 ms 6912 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6912 KB Output is correct
2 Correct 7 ms 6912 KB Output is correct
3 Correct 7 ms 7040 KB Output is correct
4 Correct 7 ms 6912 KB Output is correct
5 Correct 8 ms 6912 KB Output is correct
6 Correct 8 ms 6912 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7040 KB Output is correct
2 Correct 8 ms 7040 KB Output is correct
3 Correct 11 ms 7168 KB Output is correct
4 Correct 13 ms 7424 KB Output is correct
5 Correct 12 ms 7296 KB Output is correct
6 Correct 12 ms 7168 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7424 KB Output is correct
2 Correct 45 ms 8312 KB Output is correct
3 Correct 72 ms 9208 KB Output is correct
4 Correct 86 ms 9540 KB Output is correct
5 Correct 158 ms 11128 KB Output is correct
6 Correct 139 ms 9148 KB Output is correct