oj.uz

Submission #646139

# Submission time Handle Problem Language Result Execution time Memory
646139 2022-09-28T18:45:56 Z Hacv16 Zamjena (COCI18_zamjena) C++17
0 / 70
 34 ms 65536 KB 
#include<bits/stdc++.h>
using namespace std;

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

const int MAX = 2e6 + 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, dig[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);
    }

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

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

    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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -