# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
366261 |
2021-02-13T17:19:31 Z |
wiwiho |
Zamjena (COCI18_zamjena) |
C++14 |
|
109 ms |
6892 KB |
#include <bits/stdc++.h>
#define eb emplace_back
#define printv(a, b) {\
bool ps = false;\
for(auto pv : a){\
if(ps) b << ' '; ps = true;\
b << pv;\
}\
b << "\n";\
}
using namespace std;
map<string, int> id;
int ts = 1;
void read(vector<int>& a){
for(int i = 0; i < a.size(); i++){
string s;
cin >> s;
if('0' <= s[0] && s[0] <= '9'){
a[i] = -stoi(s);
continue;
}
if(id.find(s) == id.end()) id[s] = ++ts;
a[i] = id[s];
}
}
vector<vector<int>> g;
vector<int> v;
void dfs(int now, int tv){
v[now] = tv;
for(int i : g[now]){
if(v[i] != -1) continue;
dfs(i, tv);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
map<string, int> id;
vector<int> a(n), b(n);
read(a);
read(b);
//printv(a, cerr);
//printv(b, cerr);
g.resize(ts + 1);
for(int i = 0; i < n; i++){
if(a[i] < 0 || b[i] < 0) continue;
g[a[i]].eb(b[i]);
g[b[i]].eb(a[i]);
}
v.resize(ts + 1, -1);
for(int i = 0; i < n; i++){
//cerr << i << " ";
//printv(v, cerr);
if(a[i] < 0 && b[i] < 0){
if(a[i] != b[i]) return cout << "NE\n", 0;
continue;
}
if(a[i] < 0){
if(v[b[i]] != -1){
//cerr << i << " " << v[b[i]] << " " << -a[i] << "\n";
if(v[b[i]] != -a[i]) return cout << "NE\n", 0;
continue;
}
dfs(b[i], -a[i]);
}
if(b[i] < 0){
if(v[a[i]] != -1){
if(v[a[i]] != -b[i]) return cout << "NE\n", 0;
//cerr << i << " " << v[a[i]] << " " << -b[i] << "\n";
continue;
}
dfs(a[i], -b[i]);
}
}
cout << "DA\n";
return 0;
}
Compilation message
zamjena.cpp: In function 'void read(std::vector<int>&)':
zamjena.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for(int i = 0; i < a.size(); i++){
| ~~^~~~~~~~~~
# |
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 |
268 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 |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
0 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 |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
0 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
492 KB |
Output is correct |
2 |
Correct |
2 ms |
364 KB |
Output is correct |
3 |
Correct |
4 ms |
620 KB |
Output is correct |
4 |
Correct |
5 ms |
748 KB |
Output is correct |
5 |
Correct |
4 ms |
620 KB |
Output is correct |
6 |
Correct |
4 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
1260 KB |
Output is correct |
2 |
Correct |
35 ms |
2284 KB |
Output is correct |
3 |
Correct |
62 ms |
3948 KB |
Output is correct |
4 |
Correct |
63 ms |
4204 KB |
Output is correct |
5 |
Correct |
109 ms |
6892 KB |
Output is correct |
6 |
Correct |
76 ms |
3948 KB |
Output is correct |