oj.uz

Submission #305097

# Submission time Handle Problem Language Result Execution time Memory
305097 2020-09-22T15:08:20 Z phathnv Zamjena (COCI18_zamjena) C++11
70 / 70
 205 ms 60700 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 5e5 + 1;

int n;
string a[2][N];

vector <int> adj[N * 2];
map <string, int> idx;
int cur, d[2 * N];
bool noSolution;

void readInput(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[0][i];
    for(int i = 1; i <= n; i++)
        cin >> a[1][i];
}

void dfs(int u, int val){
    if (d[u] == val)
        return;
    if (d[u] != 0 && d[u] != val){
        noSolution = 1;
        return;
    }
    d[u] = val;
    for(int v : adj[u])
        dfs(v, val);
}

void solve(){
    for(int i = 0; i < 2; i++)
        for(int j = 1; j <= n; j++){
            if (isdigit(a[i][j][0]))
                continue;
            if (idx[a[i][j]] == 0)
                idx[a[i][j]] = ++cur;
        }
    for(int i = 1; i <= n; i++)
        if (!isdigit(a[0][i][0]) && !isdigit(a[1][i][0])){
            int u = idx[a[0][i]], v = idx[a[1][i]];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    for(int i = 1; i <= n; i++)
        if (isdigit(a[0][i][0]) && !isdigit(a[1][i][0]))
            dfs(idx[a[1][i]], atoi(a[0][i].c_str()));
        else if (!isdigit(a[0][i][0]) && isdigit(a[1][i][0]))
            dfs(idx[a[0][i]], atoi(a[1][i].c_str()));

    for(int i = 1; i <= n; i++)
        if (isdigit(a[0][i][0]) && isdigit(a[1][i][0]) && a[0][i] != a[1][i])
            noSolution = 1;

    cout << (noSolution? "NE" : "DA");
}

int main(){
    readInput();
    solve();
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 55168 KB Output is correct
2 Correct 33 ms 55172 KB Output is correct
3 Correct 34 ms 55160 KB Output is correct
4 Correct 33 ms 55160 KB Output is correct
5 Correct 36 ms 55164 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 55168 KB Output is correct
2 Correct 33 ms 55168 KB Output is correct
3 Correct 34 ms 55168 KB Output is correct
4 Correct 34 ms 55160 KB Output is correct
5 Correct 35 ms 55288 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 55160 KB Output is correct
2 Correct 34 ms 55168 KB Output is correct
3 Correct 35 ms 55160 KB Output is correct
4 Correct 33 ms 55160 KB Output is correct
5 Correct 34 ms 55160 KB Output is correct
6 Correct 34 ms 55224 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 55168 KB Output is correct
2 Correct 35 ms 55168 KB Output is correct
3 Correct 40 ms 55416 KB Output is correct
4 Correct 40 ms 55416 KB Output is correct
5 Correct 39 ms 55416 KB Output is correct
6 Correct 39 ms 55288 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 55928 KB Output is correct
2 Correct 76 ms 56824 KB Output is correct
3 Correct 113 ms 58104 KB Output is correct
4 Correct 130 ms 58360 KB Output is correct
5 Correct 205 ms 60700 KB Output is correct
6 Correct 145 ms 58104 KB Output is correct