oj.uz

Submission #197539

# Submission time Handle Problem Language Result Execution time Memory
197539 2020-01-21T15:41:07 Z Windazz Zamjena (COCI18_zamjena) C++17
56 / 70
 340 ms 46036 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 31736 KB Output is correct
2 Correct 28 ms 31608 KB Output is correct
3 Correct 33 ms 31736 KB Output is correct
4 Correct 28 ms 31736 KB Output is correct
5 Correct 34 ms 31864 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 31708 KB Output is correct
2 Correct 38 ms 31736 KB Output is correct
3 Correct 33 ms 31708 KB Output is correct
4 Correct 33 ms 31736 KB Output is correct
5 Correct 33 ms 31760 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 31736 KB Output is correct
2 Correct 33 ms 31736 KB Output is correct
3 Correct 32 ms 31736 KB Output is correct
4 Incorrect 32 ms 31736 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 31992 KB Output is correct
2 Correct 35 ms 31992 KB Output is correct
3 Correct 40 ms 32496 KB Output is correct
4 Correct 48 ms 32632 KB Output is correct
5 Correct 50 ms 32504 KB Output is correct
6 Correct 37 ms 32120 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 33912 KB Output is correct
2 Correct 103 ms 36044 KB Output is correct
3 Correct 128 ms 39620 KB Output is correct
4 Correct 181 ms 39152 KB Output is correct
5 Correct 340 ms 46036 KB Output is correct
6 Correct 219 ms 39792 KB Output is correct