oj.uz

Submission #646143

# Submission time Handle Problem Language Result Execution time Memory
646143 2022-09-28T18:53:59 Z Hacv16 Zamjena (COCI18_zamjena) C++17
70 / 70
 83 ms 19700 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 7 ms 12756 KB Output is correct
3 Correct 7 ms 12856 KB Output is correct
4 Correct 7 ms 12856 KB Output is correct
5 Correct 7 ms 12756 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12756 KB Output is correct
2 Correct 8 ms 12836 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 6 ms 12756 KB Output is correct
5 Correct 6 ms 12764 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 6 ms 12756 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 7 ms 12756 KB Output is correct
5 Correct 6 ms 12756 KB Output is correct
6 Correct 7 ms 12756 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12884 KB Output is correct
2 Correct 7 ms 12884 KB Output is correct
3 Correct 8 ms 13140 KB Output is correct
4 Correct 8 ms 13268 KB Output is correct
5 Correct 8 ms 13152 KB Output is correct
6 Correct 9 ms 13144 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13780 KB Output is correct
2 Correct 22 ms 14928 KB Output is correct
3 Correct 34 ms 16572 KB Output is correct
4 Correct 43 ms 16996 KB Output is correct
5 Correct 83 ms 19700 KB Output is correct
6 Correct 68 ms 16924 KB Output is correct