Submission #197028

#	Time	Username	Problem	Language	Result	Execution time	Memory
197028		quocnguyen1012	Zamjena (COCI18_zamjena)	C++14	70 / 70	218 ms	23288 KiB

zamjena

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

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