Submission #170606

#	Time	Username	Problem	Language	Result	Execution time	Memory
170606		BigChungus	Zamjena (COCI18_zamjena)	C++14	70 / 70	221 ms	14940 KiB

zamjena

#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 (stderr)

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

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14