Submission #646143

#	Time	Username	Problem	Language	Result	Execution time	Memory
646143		Hacv16	Zamjena (COCI18_zamjena)	C++17	70 / 70	83 ms	19700 KiB

zamjena

#include<bits/stdc++.h>
using namespace std;

typedef int ll;
typedef pair<int, int> pii;

const int MAX = 2e5 + 15;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

#define pb push_back
#define sz(x) (int) x.size()
#define fr first
#define sc second
#define mp make_pair
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << #x << ": " << "[ " << x << " ]\n"

ll n, pai[MAX], sze[MAX], dig[MAX];
bool ans = true;

string a[MAX], b[MAX];
map<string, vector<int>> pos;

bool isNum(string s){
    for(auto c : s)
        if(c < '0' || c > '9') return false;
    return true;
}

ll find(ll u){
    return pai[u] = (pai[u] == u ? u : find(pai[u]));
}

void join(ll u, ll v){
    u = find(u), v = find(v);
    if(u == v) return;
    if(sze[v] > sze[u]) swap(u, v);
    pai[v] = u, sze[u] += sze[v];

    if(dig[u] != dig[v] && dig[u] != -1 && dig[v] != -1)
        ans = false;

    if(dig[u] == -1 && dig[v] != -1) 
        dig[u] = dig[v];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 

    cin >> n;

    for(int i = 1; i <= 2 * n; i++)
        pai[i] = i, sze[i] = 1;

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

        if(isNum(a[i])) 
            dig[i] = stoll(a[i]);
        else
            pos[a[i]].pb(i), dig[i] = -1;
    }

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

        if(isNum(b[i]))
            dig[i + n] = stoll(b[i]);
        else
            pos[b[i]].pb(i + n), dig[i + n] = -1;
    }

    for(int i = 1; i <= n; i++)
        join(i, i + n);

    for(auto it = pos.begin(); it != pos.end(); ++it){
        for(int i = 1; i < sz(it -> sc); i++){
            join(it->sc[i], it->sc[i - 1]);
        }
    }

    cout << (ans ? "DA" : "NE") << '\n';

    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14