oj.uz

Submission #82262

# Submission time Handle Problem Language Result Execution time Memory
82262 2018-10-29T16:48:13 Z Milki Zamjena (COCI18_zamjena) C++14
56 / 70
 108 ms 16576 KB 
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)

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

const int MAXN = 5e4 + 5;

unordered_map<string, string> val;
unordered_map<string, vector<string> > isti;

int n;
string a[MAXN], b[MAXN];

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

    cin >> n;
    REP(i, n) cin >> a[i];
    REP(i, n) cin >> b[i];

    REP(i, n){
        if(a[i] == b[i]) continue;
        if(a[i][0] >= '0' && a[i][0] <= '9' && b[i][0] >= '0' && b[i][0] <= '9'){
            if(a[i] != b[i]){
                cout << "NE\n";
                return 0;
            }
        }
        else if( (a[i][0] >= '0' && a[i][0] <= '9') || (b[i][0] >= '0' && b[i][0] <= '9')){
            if(a[i][0] >= '0' && a[i][0] <= '9') swap(a[i], b[i]);
            string value = val[a[i]];
            if(value != "")
                if(value != b[i]){
                    cout << "NE\n";
                    return 0;
                }

            val[a[i]] = b[i];
            for(auto it : isti[a[i]]){
                val[it] = b[i];
                for(auto it2 : isti[it])
                    val[it2] = b[i];
                isti[it].clear();
            }
            isti[a[i]].clear();
        }
        else{
            string val_a = val[a[i]], val_b = val[b[i]];
            if(val_a == "") {
                swap(val_a, val_b);
                swap(a[i], b[i]);
            }

            if(val_a == "" && val_b == ""){
                isti[a[i]].pb(b[i]);
                isti[b[i]].pb(a[i]);
            }
            else if(val_a != "" && val_b == ""){
                val[b[i]] = val_a;
                for(auto it : isti[b[i]]){
                    val[it] = val_a;
                    for(auto it2 : isti[it])
                        val[it2] = val_a;
                    isti[it].clear();
                }
                isti[b[i]].clear();
            }
            else if(val_a != val_b){
                cout << "NE\n";
                return 0;
            }
        }
    }
    cout << "DA\n";
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3572 KB Output is correct
3 Correct 5 ms 3572 KB Output is correct
4 Correct 5 ms 3572 KB Output is correct
5 Correct 5 ms 3572 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3700 KB Output is correct
2 Correct 5 ms 3700 KB Output is correct
3 Correct 5 ms 3700 KB Output is correct
4 Correct 4 ms 3700 KB Output is correct
5 Correct 5 ms 3700 KB Output is correct
6 Incorrect 5 ms 3700 KB Output isn't correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3936 KB Output is correct
2 Correct 6 ms 3936 KB Output is correct
3 Correct 7 ms 4192 KB Output is correct
4 Correct 8 ms 4448 KB Output is correct
5 Correct 9 ms 4448 KB Output is correct
6 Correct 7 ms 4448 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5472 KB Output is correct
2 Correct 32 ms 7392 KB Output is correct
3 Correct 51 ms 10464 KB Output is correct
4 Correct 57 ms 10464 KB Output is correct
5 Correct 108 ms 16576 KB Output is correct
6 Correct 66 ms 16576 KB Output is correct