oj.uz

Submission #170606

# Submission time Handle Problem Language Result Execution time Memory
170606 2019-12-25T19:06:07 Z BigChungus Zamjena (COCI18_zamjena) C++14
70 / 70
 221 ms 14940 KB 
#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int N = 5e4 + 7;

bool ok(0);

string s[N], t[N];

map < int, string > m;

map < string, int > mynorm;
string invn[N];

vector < pair < string, string > > restrictii;
vector < int > adia[N];

bool viz[N];

void dfs(int nod, string &val) {
    if (m.find(nod) == m.end()) {
        m[nod] = val;
    }
    else if (m[nod] != val) {
        ok = 1;
        return;
    }
    if (viz[nod])
        return;
    viz[nod] = 1;
    for (int i : adia[nod])
        dfs(i, val);
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    int n;
    int ind(0);
    cin >> n;
    char ch;
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
        if (s[i].front() > '9' && mynorm.find(s[i]) == mynorm.end())
            mynorm[s[i]] = ++ind, invn[ind] = s[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> t[i];
        if (t[i].front() > '9' && mynorm.find(t[i]) == mynorm.end())
            mynorm[t[i]] = ++ind, invn[ind] = t[i];
    }
    for (int i = 1; i <= n; ++i) {
        if (s[i].front() <= '9' && t[i].front() <= '9') {///am verificat in ascii si da, cifrele sunt inaintea literelor
            if (s[i] != t[i])
                ok = 1;
        }
        else if (s[i].front() <= '9') {
            if (m.find(mynorm[t[i]]) == m.end())
                m[mynorm[t[i]]] = s[i];
            else if (m[mynorm[t[i]]] != s[i])
                ok = 1;
        }
        else if (t[i].front() <= '9') {
            if (m.find(mynorm[s[i]]) == m.end())
                m[mynorm[s[i]]] = t[i];
            else if (m[mynorm[s[i]]] != t[i])
                ok = 1;
        }
        else {
            adia[mynorm[s[i]]].push_back(mynorm[t[i]]);
            adia[mynorm[t[i]]].push_back(mynorm[s[i]]);
        }
    }
    for (auto i : m)
        dfs(i.first, i.second);
    if (!ok)
        cout << "DA\n";
    else
        cout << "NE\n";
    return 0;
}

Compilation message

zamjena.cpp: In function 'int main()':
zamjena.cpp:50:10: warning: unused variable 'ch' [-Wunused-variable]
     char ch;
          ^~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6392 KB Output is correct
2 Correct 9 ms 6264 KB Output is correct
3 Correct 14 ms 6676 KB Output is correct
4 Correct 15 ms 6780 KB Output is correct
5 Correct 14 ms 6644 KB Output is correct
6 Correct 13 ms 6520 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7452 KB Output is correct
2 Correct 64 ms 8720 KB Output is correct
3 Correct 109 ms 10816 KB Output is correct
4 Correct 133 ms 11128 KB Output is correct
5 Correct 221 ms 14940 KB Output is correct
6 Correct 152 ms 10640 KB Output is correct