이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = (int)1e5 + 7;
const int infint = (int)1e9;
const ll inf = (ll)1e18;
string s1[MAXN], s2[MAXN];
string val[MAXN];
vector<int> G[MAXN], comp[MAXN];
int visited[MAXN], cmp = 0, n;
void dfs(int u)
{
comp[cmp].push_back(u);
visited[u] = 1;
for (auto v : G[u])
if(!visited[v])
dfs(v);
}
unordered_map<string, int> M;
ll get(string s)
{
if(s[0] < '0' || s[0] > '9')
return 0;
else
return 1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
cin >> s1[i];
for (int i = 0; i < n; i++)
cin >> s2[i];
set<string> S;
for (int i = 0; i < n; i++)
if(get(s1[i]) == 0)
S.insert(s1[i]);
for (int i = 0; i < n; i++)
if(get(s2[i]) == 0)
S.insert(s2[i]);
int cnt = 0;
for (auto u : S)
M[u] = cnt++;
for (int i = 0; i < n; i++)
{
if(get(s1[i]) == 1)
{
if(get(s2[i]) == 1)
{
if(s1[i] != s2[i])
return cout << "NE", 0;
}
else
{
if(val[M[s2[i]]] != "" && val[M[s2[i]]] != s1[i])
return cout << "NE", 0;
val[M[s2[i]]] = s1[i];
}
}
else
{
if(get(s2[i]) == 1)
{
if(val[M[s1[i]]] != "" && val[M[s1[i]]] != s2[i])
return cout << "NE", 0;
val[M[s1[i]]] = s2[i];
}
else
{
G[M[s1[i]]].push_back(M[s2[i]]);
G[M[s2[i]]].push_back(M[s1[i]]);
}
}
}
for (int i = 0; i < cnt; i++)
if(!visited[i])
dfs(i), cmp++;
for (int i = 0; i < cmp; i++)
{
string fir;
for (auto u : comp[i])
if(val[u] != "")
fir = val[u];
if(fir == "")
continue;
for (auto u : comp[i])
if(val[u] != "" && val[u] != fir)
return cout << "NE", 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... |