이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
vector<vector<int>> g;
vector<int> picked;
vector<int> used;
vector<string> num;
string ans;
bool dfs(int v) {
used[v] = 1;
if (ans == "-1" && picked[v]) {
ans = num[v];
}
if (ans != num[v] && picked[v]) return false;
for (auto u : g[v]) {
if (!used[u]) {
if (!dfs(u)) return false;
}
}
return true;
}
int main() {
int n;
cin >> n;
int N = 0;
map<string, int> m1;
vector<string> a(n), b(n);
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n; ++i) { cin >> b[i]; }
for (int i = 0; i < n; ++i) {
int v1 = m1[a[i]];
int v2 = m1[b[i]];
if (!v1) {
v1 = ++N;
m1[a[i]] = N;
}
if (!v2) {
v2 = ++N;
m1[b[i]] = N;
}
picked.resize(N + 1);
g.resize(N + 1);
num.resize(N + 1);
num[v1] = a[i];
num[v2] = b[i];
if ('0' <= a[i][0] && a[i][0] <= '9') picked[v1] = 1;
if ('0' <= b[i][0] && b[i][0] <= '9') picked[v2] = 1;
g[v1].push_back(v2);
g[v2].push_back(v1);
}
used.resize(N + 1);
for (int i = 1; i <= N; ++i) {
if (!used[i]) {
ans = "-1";
if (!dfs(i)) {
cout << "NE";
return 0;
}
}
}
cout << "DA";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |