This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;
typedef pair <int, bool> pib;
#define F first
#define S second
#define mkp make_pair
#define pb push_back
#define sz(a) (int)a.size()
#define show(x) cerr << "# " << #x << " = " << (x) << endl
const int N = 2e5;
int n, a[N], b[N], NUM = 1000;
bool va[N], vb[N], u[N];
vector <pib> g[N];
set <int> st;
map <string, int> num;
void dfs(int v, bool var) {
u[v] = 1;
if(!var) {
st.insert(v);
}
for(pib it : g[v]) {
int to = it.F;
bool vto = it.S;
if(!u[to]) {
dfs(to, vto);
}
}
}
int main () {
ios_base :: sync_with_stdio(false);
cin >> n;
for(int i = 1; i <= n; ++i) {
string s;
cin >> s;
if('0' <= s[0] && s[0] <= '9') { // esli eto chislo
a[i] = stoi(s);
}
else { // esli eto variable
if(num[s] == 0) { // esli u nego netu nomera
num[s] = ++NUM;
}
a[i] = num[s];
va[i] = 1;
}
}
for(int i = 1; i <= n; ++i) {
string s;
cin >> s;
if('0' <= s[0] && s[0] <= '9') { // esli eto chislo
b[i] = stoi(s);
}
else { // esli eto variable
if(num[s] == 0) { // esli u nego netu nomera
num[s] = ++NUM;
}
b[i] = num[s];
vb[i] = 1;
}
}
// sozdaem graph
for(int i = 1; i <= n; ++i) {
g[a[i]].pb(mkp(b[i], vb[i]));
g[b[i]].pb(mkp(a[i], va[i]));
}
// mutim dfs
for(int i = 1; i <= n; ++i) {
if(!u[a[i]]) {
dfs(a[i], va[i]);
if(sz(st) > 1) {
cout << "NE";
return 0;
}
st.clear();
}
}
cout << "DA";
return 0;
}
# | 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... |