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 <unordered_map>
#include <vector>
using namespace std;
const long long Nmax=50000;
long long n, ind, sol[Nmax*2];
string v[Nmax];
unordered_map <long long, long long> m;
vector <long long> ad[Nmax*2];
bool ok=1;
void dfs (long long nod, long long val){
if (sol[nod]==0){
sol[nod]=val;
for (long long i=0; i<ad[nod].size(); i++)
dfs(ad[nod][i], val);
}
else if (sol[nod]!=val){
ok=0; //cout<<nod<<' '<<val<<' ';
}
}
void eq (string &s, long long val){
long long h=0;
for (long long i=0; i<s.size(); i++)
h=h*26+s[i]-'a';
if (m.count(h)==0)
m[h]=ind++;
dfs(m[h], val+1);
}
void check (string &s1, string &s2){
long long h1=0, h2=0;
for (long long i=0; i<s1.size(); i++)
h1=h1*26+s1[i]-'a';
for (long long i=0; i<s2.size(); i++)
h2=h2*26+s2[i]-'a';
if (m.count(h1)==0)
m[h1]=ind++;
if (m.count(h2)==0)
m[h2]=ind++;
if (sol[m[h1]]!=0 && sol[m[h2]]!=0 && sol[m[h1]]!=sol[m[h2]])
ok=0;
else if (sol[m[h1]]==0 && sol[m[h2]]!=0)
dfs(m[h1], sol[m[h2]]);
else if (sol[m[h2]]==0 && sol[m[h1]]!=0)
dfs(m[h2], sol[m[h1]]);
ad[m[h1]].push_back(m[h2]);
ad[m[h2]].push_back(m[h1]);
}
int main()
{
cin>>n;
for (long long i=0; i<n; i++)
cin>>v[i];
string s;
for (long long i=0; i<n && ok; i++){
cin>>s;
long long v1=-1, v2=-1;
if (v[i][0]<='9'){
v1=0;
for (int j=0; j<v[i].size(); j++)
v1=v1*10+v[i][j]-'0';
}
if (s[0]<='9'){
v2=0;
for (int j=0; j<s.size(); j++)
v2=v2*10+s[j]-'0';
}
if (v1!=-1 && v2!=-1 && v1!=v2)
ok=0;
else if (v1!=v2){
if (v1==-1)
eq(v[i], v2);
else eq(s, v1);
}
else if (v1==-1)
check(v[i], s);
}
if (ok)
cout<<"DA";
else cout<<"NE";
return 0;
}
Compilation message (stderr)
zamjena.cpp: In function 'void dfs(long long int, long long int)':
zamjena.cpp:17:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (long long i=0; i<ad[nod].size(); i++)
| ~^~~~~~~~~~~~~~~
zamjena.cpp: In function 'void eq(std::string&, long long int)':
zamjena.cpp:26:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for (long long i=0; i<s.size(); i++)
| ~^~~~~~~~~
zamjena.cpp: In function 'void check(std::string&, std::string&)':
zamjena.cpp:34:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (long long i=0; i<s1.size(); i++)
| ~^~~~~~~~~~
zamjena.cpp:36:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (long long i=0; i<s2.size(); i++)
| ~^~~~~~~~~~
zamjena.cpp: In function 'int main()':
zamjena.cpp:62:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for (int j=0; j<v[i].size(); j++)
| ~^~~~~~~~~~~~
zamjena.cpp:67:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int j=0; j<s.size(); j++)
| ~^~~~~~~~~
# | 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... |