Submission #1343012

#TimeUsernameProblemLanguageResultExecution timeMemory
1343012thnhannZamjena (COCI18_zamjena)C++20
70 / 70
73 ms35676 KiB
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define ill pair<ll,ll>
#define el cout<<'\n'
#define int long long

const ll mod=1e9+7;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
const int nmax=5e5;
const int inf =2e9;

void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

using namespace std;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r)
{
    return uniform_int_distribution<int>(l, r) (rd);
}

int lab[nmax];
int val[nmax];
bool has_val[nmax];
int timer = 0;
map<string, int> mp;

int get_id(const string& s) {
    if (!mp.count(s)) {
        mp[s] = ++timer;
        lab[timer] = -1;
        has_val[timer] = false;
    }
    return mp[s];
}

int find_set(int u) {
    return lab[u] < 0 ? u : lab[u] = find_set(lab[u]);
}

bool union_sets(int u, int v) {
    u = find_set(u);
    v = find_set(v);
    if (u == v) return true;
    
    if (has_val[u] && has_val[v] && val[u] != val[v]) return false;
    
    if (lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
    if (has_val[v]) {
        val[u] = val[v];
        has_val[u] = true;
    }
    return true;
}

bool is_num(const string &s) {
    if (s.empty()) return false;
    return isdigit(s[0]) || (s.size() > 1 && s[0] == '-');
}

string a[nmax], b[nmax];

signed main()
{
   ios::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);

   int n;
   if (!(cin >> n)) return 0;

   for(int i = 1; i <= n; i++) cin >> a[i];
   for(int i = 1; i <= n; i++) cin >> b[i];

   bool ok = true;

   for(int i = 1; i <= n; i++) {
       bool a_num = is_num(a[i]);
       bool b_num = is_num(b[i]);

       if (a_num && b_num) {
           if (stoll(a[i]) != stoll(b[i])) ok = false;
       } else if (a_num && !b_num) {
           int u = get_id(b[i]);
           int root = find_set(u);
           int num = stoll(a[i]);
           if (has_val[root] && val[root] != num) ok = false;
           val[root] = num;
           has_val[root] = true;
       } else if (!a_num && b_num) {
           int u = get_id(a[i]);
           int root = find_set(u);
           int num = stoll(b[i]);
           if (has_val[root] && val[root] != num) ok = false;
           val[root] = num;
           has_val[root] = true;
       } else {
           int u = get_id(a[i]);
           int v = get_id(b[i]);
           if (!union_sets(u, v)) ok = false;
       }
   }

   if (ok) {
       cout << "DA"; el;
   } else {
       cout << "NE"; el;
   }

}
// "Can i get a kiss? And can u make it last forever?"
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...