oj.uz

Submission #197028

# Submission time Handle Problem Language Result Execution time Memory
197028 2020-01-18T07:42:17 Z quocnguyen1012 Zamjena (COCI18_zamjena) C++14
70 / 70
 218 ms 23288 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 2e5 + 5;

struct DSU
{
  vector<int> lab;
  void init(int n)
  {
    lab.resize(n + 5);
    fill(begin(lab), end(lab), -1);
  }
  int finds(int u)
  {
    if (lab[u] < 0) return u;
    return lab[u] = finds(lab[u]);
  }
  void merges(int u, int v)
  {
    u = finds(u); v = finds(v);
    if (u == v) return;
    if (lab[v] < lab[u]) swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
  }
}dsu;

map<string, int> ma;
int cnt = 0;
map<string, bool> ok;
string a[maxn], b[maxn];
int N;
string val[maxn];

bool isdigit(char x)
{
  return ('0' <= x && x <= '9');
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  int cnt = 0;
  cin >> N;
  for (int i = 1; i <= N; ++i){
    cin >> a[i];
    if (!isdigit(a[i][0])){
      if (ma[a[i]] == 0)ma[a[i]] = ++cnt;
    }
  }
  for (int i = 1; i <= N; ++i){
    cin >> b[i];
    if (!isdigit(b[i][0])){
      if (ma[b[i]] == 0)ma[b[i]] = ++cnt;
    }
  }
  //for (int i = 1; i <= N; ++i)cerr << isdigit(a[i][0]) << ' ' << isdigit(b[i][0]) << '\n';
  //return 0;
  dsu.init(cnt);
  for (int i = 1; i <= N; ++i){
    if (isdigit(a[i][0]) == 0 && isdigit(b[i][0]) == 0){
      dsu.merges(ma[a[i]], ma[b[i]]);
      //cerr << i << '\n';
    }
  }
  for (int i = 1; i <= N; ++i){
    if (isdigit(a[i][0]) && isdigit(b[i][0])){
      //cerr << i << '\n';
      if (a[i] != b[i]){
        cout << "NE";
        return 0;
      }
    }
    else if (isdigit(a[i][0])){
      val[dsu.finds(ma[b[i]])] = a[i];
      //cerr << i << '\n';
    }
    else if (isdigit(b[i][0])){
      val[dsu.finds(ma[a[i]])] = b[i];
    }
  }
  for (int i = 1; i <= N; ++i){
    if (isdigit(a[i][0]) && isdigit(b[i][0])){
      if (a[i] != b[i]){
        cout << "NE";
        return 0;
      }
    }
    else if (isdigit(a[i][0])){
      if (val[dsu.finds(ma[b[i]])] != a[i]){
        cout << "NE";
        //cerr << i;
        return 0;
      }
    }
    else if (isdigit(b[i][0])){
      if (val[dsu.finds(ma[a[i]])] != b[i]){
        cout << "NE";
        return 0;
      }
    }
    else{
      if (val[dsu.finds(ma[a[i]])] != val[dsu.finds(ma[b[i]])]){
        cout << "NE";
        return 0;
      }
    }
  }
  cout << "DA";
}

Compilation message

zamjena.cpp: In function 'int main()':
zamjena.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
zamjena.cpp:53:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19064 KB Output is correct
2 Correct 19 ms 19192 KB Output is correct
3 Correct 20 ms 19192 KB Output is correct
4 Correct 19 ms 19064 KB Output is correct
5 Correct 19 ms 19192 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19192 KB Output is correct
2 Correct 19 ms 19064 KB Output is correct
3 Correct 20 ms 19064 KB Output is correct
4 Correct 18 ms 19096 KB Output is correct
5 Correct 20 ms 19192 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19064 KB Output is correct
2 Correct 20 ms 19064 KB Output is correct
3 Correct 19 ms 19064 KB Output is correct
4 Correct 19 ms 19192 KB Output is correct
5 Correct 20 ms 19084 KB Output is correct
6 Correct 20 ms 19064 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19192 KB Output is correct
2 Correct 20 ms 19192 KB Output is correct
3 Correct 26 ms 19320 KB Output is correct
4 Correct 25 ms 19320 KB Output is correct
5 Correct 25 ms 19320 KB Output is correct
6 Correct 24 ms 19192 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 19704 KB Output is correct
2 Correct 63 ms 20404 KB Output is correct
3 Correct 85 ms 21500 KB Output is correct
4 Correct 106 ms 21496 KB Output is correct
5 Correct 218 ms 23288 KB Output is correct
6 Correct 142 ms 21132 KB Output is correct