oj.uz

Submission #85223

# Submission time Handle Problem Language Result Execution time Memory
85223 2018-11-19T00:03:23 Z FutymyClone Zamjena (COCI18_zamjena) C++14
70 / 70
 122 ms 6920 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n, a[N], b[N], f[N], cnt = 1000;
map <string, int> mm;

struct disj {
    int par[N];
    void init (int n) {
        for (int i = 1; i <= n; i++) par[i] = i;
    }

    int Find (int x) {
        return par[x] == x ? x : par[x] = Find(par[x]);
    }

    bool same (int x, int y) {
        return Find(x) == Find(y);
    }

    void join (int x, int y) {
        x = Find(x); y = Find(y);
        if (x == y) return;
        par[y] = x;
    }
} dsu;

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        if (s[0] >= '0' && s[0] <= '9') {
            int sum = 0;
            for (int j = 0; j < s.length(); j++) sum = sum * 10 + (s[j] - '0');
            a[i] = sum;
        }
        else {
            if (!mm.count(s)) mm[s] = ++cnt;
            a[i] = mm[s];
        }
    }

    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        if (s[0] >= '0' && s[0] <= '9') {
            int sum = 0;
            for (int j = 0; j < s.length(); j++) sum = sum * 10 + (s[j] - '0');
            b[i] = sum;
        }
        else {
            if (!mm.count(s)) mm[s] = ++cnt;
            b[i] = mm[s];
        }
    }

    dsu.init(200000);
    for (int i = 1; i <= n; i++) dsu.join(a[i], b[i]);
    for (int i = 0; i <= 1000; i++) f[dsu.Find(i)]++;
    for (int i = 0; i < N; i++) if (f[i] >= 2) return cout << "NE", 0;
    cout << "DA";
    return 0;
}

Compilation message

zamjena.cpp: In function 'int main()':
zamjena.cpp:38:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < s.length(); j++) sum = sum * 10 + (s[j] - '0');
                             ~~^~~~~~~~~~~~
zamjena.cpp:51:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < s.length(); j++) sum = sum * 10 + (s[j] - '0');
                             ~~^~~~~~~~~~~~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1416 KB Output is correct
2 Correct 3 ms 1424 KB Output is correct
3 Correct 2 ms 1428 KB Output is correct
4 Correct 2 ms 1428 KB Output is correct
5 Correct 3 ms 1432 KB Output is correct
6 Correct 3 ms 1436 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1440 KB Output is correct
2 Correct 4 ms 1452 KB Output is correct
3 Correct 6 ms 1712 KB Output is correct
4 Correct 7 ms 1736 KB Output is correct
5 Correct 7 ms 1760 KB Output is correct
6 Correct 6 ms 1760 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2108 KB Output is correct
2 Correct 32 ms 3040 KB Output is correct
3 Correct 53 ms 4216 KB Output is correct
4 Correct 66 ms 4804 KB Output is correct
5 Correct 122 ms 6920 KB Output is correct
6 Correct 73 ms 6920 KB Output is correct