oj.uz

Submission #646140

# Submission time Handle Problem Language Result Execution time Memory
646140 2022-09-28T18:46:38 Z Hacv16 Zamjena (COCI18_zamjena) C++17
56 / 70
 69 ms 20152 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, 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 Correct 7 ms 12756 KB Output is correct
2 Incorrect 7 ms 12856 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12860 KB Output is correct
2 Correct 6 ms 12756 KB Output is correct
3 Correct 7 ms 12972 KB Output is correct
4 Correct 7 ms 12756 KB Output is correct
5 Correct 7 ms 12756 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 6 ms 12856 KB Output is correct
5 Correct 8 ms 12816 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 12960 KB Output is correct
2 Correct 9 ms 12864 KB Output is correct
3 Correct 8 ms 13140 KB Output is correct
4 Correct 9 ms 13304 KB Output is correct
5 Correct 9 ms 13140 KB Output is correct
6 Correct 8 ms 13140 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 13876 KB Output is correct
2 Correct 22 ms 15036 KB Output is correct
3 Correct 36 ms 16812 KB Output is correct
4 Correct 46 ms 17336 KB Output is correct
5 Correct 69 ms 20152 KB Output is correct
6 Correct 56 ms 17260 KB Output is correct