#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 |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
492 KB |
Output is correct |
2 |
Correct |
2 ms |
492 KB |
Output is correct |
3 |
Correct |
10 ms |
1004 KB |
Output is correct |
4 |
Correct |
10 ms |
1004 KB |
Output is correct |
5 |
Correct |
6 ms |
1004 KB |
Output is correct |
6 |
Correct |
5 ms |
876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
2152 KB |
Output is correct |
2 |
Correct |
32 ms |
4104 KB |
Output is correct |
3 |
Correct |
58 ms |
6676 KB |
Output is correct |
4 |
Correct |
80 ms |
7960 KB |
Output is correct |
5 |
Correct |
134 ms |
11788 KB |
Output is correct |
6 |
Correct |
82 ms |
7852 KB |
Output is correct |