oj.uz

답안 #81685

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
81685 2018-10-26T07:29:49 Z Saboon Zamjena (COCI18_zamjena) C++14
56 / 70
 1000 ms 42332 KB 
#include <iostream>
#include <sstream>
#include <queue>
#include <stack>
#include <vector>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <iomanip>
#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn = 5e4 + 37;

map <string, int> mp;
map <string, vector <string> > v;

string s[maxn], t[maxn];

int integer (string s) {
    stringstream geek (s);
    int x = 0;
    geek >> x;
    return x;
}

bool isinteger (string s) {
    if ((int)(s[0] - '0') <= 10)
        return 1;
    return 0;
}

void dfs (string now, int x) {
    mp[now] = x;
    for (auto w : v[now])
        if (!mp.count (w))
            dfs (w, x);
}

int main() {
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> s[i];
    for (int i = 0; i < n; i++)
        cin >> t[i];
    for (int k = 1; k <= 10; k++) {
        for (int i = 0; i < n; i++) {
            if (isinteger (s[i])) {
                if (isinteger (t[i])) {
                    if (s[i] != t[i]) {
                        return cout << "NE" << endl, 0;
                    }
                }
                else {
                    int x = integer (s[i]);
                    if (!mp.count (t[i])) {
                        dfs (t[i], x);
                    }
                    if (!mp.count (t[i]) or mp[t[i]] == x)
                        mp[t[i]] = x;
                    else
                        return cout << "NE" << endl, 0;
                }
            }
            else {
                if (isinteger (t[i])) {
                    int x = integer (t[i]);
                    if (!mp.count (s[i])) {
                        dfs (s[i], x);
                    }
                    if (!mp.count (s[i]) or mp[s[i]] == x)
                        mp[s[i]] = x;
                    else
                        return cout << "NE" << endl, 0;
                }
                else {
                    if (mp.count (s[i])) {
                        if (mp.count (t[i])) {
                            if (mp[s[i]] != mp[t[i]])
                                return cout << "NE" << endl, 0;
                        }
                        else {
                            mp[t[i]] = mp[s[i]];
                        }
                    }
                    else if (mp.count (t[i])) {
                        mp[s[i]] = mp[t[i]];
                    }
                    v[s[i]].PB (t[i]);
                    v[t[i]].PB (s[i]);
                }
            }
        }
    }
    cout << "DA" << endl;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3448 KB Output is correct
2 Correct 4 ms 3608 KB Output is correct
3 Correct 4 ms 3608 KB Output is correct
4 Correct 5 ms 3608 KB Output is correct
5 Correct 5 ms 3608 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3608 KB Output is correct
2 Correct 4 ms 3608 KB Output is correct
3 Correct 4 ms 3608 KB Output is correct
4 Correct 5 ms 3608 KB Output is correct
5 Correct 4 ms 3608 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3608 KB Output is correct
2 Correct 5 ms 3608 KB Output is correct
3 Correct 4 ms 3608 KB Output is correct
4 Correct 5 ms 3608 KB Output is correct
5 Correct 6 ms 3656 KB Output is correct
6 Correct 4 ms 3716 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 4816 KB Output is correct
2 Correct 16 ms 4816 KB Output is correct
3 Correct 9 ms 4816 KB Output is correct
4 Correct 10 ms 4816 KB Output is correct
5 Correct 68 ms 6240 KB Output is correct
6 Correct 9 ms 6240 KB Output is correct

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 6240 KB Output is correct
2 Correct 490 ms 23036 KB Output is correct
3 Correct 165 ms 23036 KB Output is correct
4 Correct 72 ms 23036 KB Output is correct
5 Execution timed out 1069 ms 42332 KB Time limit exceeded
6 Halted 0 ms 0 KB -