Submission #197539

#	Time	Username	Problem	Language	Result	Execution time	Memory
197539		Windazz	Zamjena (COCI18_zamjena)	C++17	56 / 70	340 ms	46036 KiB

zamjena

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define x first
#define y second
#define ndl '\n'
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)x.size()
#define bit __builtin_popcount
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;
using namespace __gnu_pbds;

template<typename T> using indexed_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<int, ull> piu;
typedef vector<vector<int>> matrix;

const ll INF = 1e18 + 123;
const ld EPS = 1e-9;
const int inf = 1e9 + 123;
const int MOD = 1e9 + 7;
const int N = 5e5 + 13;
const int M = 1e6 + 123;
const double pi = acos(-1.0);
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

string a[N], b[N];

map<string, vector<string> > g;

map<string, string> num;

void dfs(string v){
    for (string to : g[v]){
        if (num[to].empty()){
            num[to] = num[v];
            dfs(to);
        }
        else if (num[to] != num[v]){
            cout << "NE";
            exit(0);
        }
    }
}

int main(){
    #ifdef KAZAKH
        freopen("input.txt", "r", stdin);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;

    for (int i = 0; i <= 1000; i++){
        auto s = to_string(i);
        num[s] = s;
    }
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++){
        cin >> b[i];
    }
    vector<string> z;
    for (int i = 1; i <= n; i++){
        if (num[a[i]].empty() && num[b[i]].empty()){
            g[a[i]].pb(b[i]);
            g[b[i]].pb(a[i]);
            continue;
        }
        if (num[a[i]].empty()){
            num[a[i]] = num[b[i]];
            z.pb(a[i]);
        }
        if (num[b[i]].empty()){
            num[b[i]] = num[a[i]];
            z.pb(b[i]);
        }
        if (num[a[i]] != num[b[i]]){
            cout << "NE";
            return 0;
        }
    }
    for (auto p : z){
        dfs(p);
    }
    cout << "DA";
    return 0;
}

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