제출 #305097

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
305097		phathnv	Zamjena (COCI18_zamjena)	C++11	70 / 70	205 ms	60700 KiB

zamjena

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14