# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
756577 |
2023-06-12T00:28:28 Z |
pcc |
Zamjena (COCI18_zamjena) |
C++14 |
|
66 ms |
8136 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
const int mxn = 5e5+10;
int dsu[mxn*2],sz[mxn*2],cnt[mxn*2];
int root(int k){
return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}
void onion(int a,int b){
a = root(a),b = root(b);
if(a == b)return;
if(sz[a]<sz[b])swap(a,b);
dsu[b] = a;
sz[a] += sz[b];
cnt[a] += cnt[b];
return;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n;
cin>>n;
string a[n],b[n];
vector<string> all;
for(auto &i:a)cin>>i,all.push_back(i);
for(auto &i:b)cin>>i,all.push_back(i);
sort(all.begin(),all.end());
all.resize(unique(all.begin(),all.end())-all.begin());
for(int i = 0;i<all.size();i++){
dsu[i] = i;
sz[i] = 1;
if(all[i][0]>='0'&&all[i][0]<='9')cnt[i] = 1;
}
for(int i = 0;i<n;i++){
if(a[i] == b[i])continue;
int ta = lower_bound(all.begin(),all.end(),a[i])-all.begin();
int tb = lower_bound(all.begin(),all.end(),b[i])-all.begin();
onion(ta,tb);
}
for(int i = 0 ;i<all.size();i++){
if(dsu[i] == i){
if(cnt[i]>1){
cout<<"NE";
return 0;
}
}
}
cout<<"DA";
return 0;
}
Compilation message
zamjena.cpp: In function 'int main()':
zamjena.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i = 0;i<all.size();i++){
| ~^~~~~~~~~~~
zamjena.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i = 0 ;i<all.size();i++){
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
3 ms |
860 KB |
Output is correct |
4 |
Correct |
3 ms |
852 KB |
Output is correct |
5 |
Correct |
3 ms |
852 KB |
Output is correct |
6 |
Correct |
3 ms |
856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
2132 KB |
Output is correct |
2 |
Correct |
20 ms |
3920 KB |
Output is correct |
3 |
Correct |
35 ms |
4736 KB |
Output is correct |
4 |
Correct |
43 ms |
7376 KB |
Output is correct |
5 |
Correct |
66 ms |
8136 KB |
Output is correct |
6 |
Correct |
51 ms |
8112 KB |
Output is correct |