oj.uz

Submission #105376

# Submission time Handle Problem Language Result Execution time Memory
105376 2019-04-11T15:50:32 Z leonarda Zamjena (COCI18_zamjena) C++14
70 / 70
 523 ms 24184 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> pi;
typedef long long int lint;
const int inf = 0x3f3f3f3f;
const int maxn = 50000 + 10;

int n; 
string a[maxn], b[maxn];
map< string, vector< int > > c, d;
map< string, bool > memo;
map< string, vector< string > > isti;
bool ok = 1;

bool isNumber(string t) {
	if(t[0] >= '0' and t[0] <= '9') return 1;
	return 0;
}

void dfs(string word, string number) {
	if(!ok) return;
	if(memo[word]) return;
	memo[word] = 1;
	
	for(int i = 0; i < isti[word].size(); ++i) {
		if(isNumber(isti[word][i]) and isti[word][i] != number) ok = 0;
		if(!ok) return;
		if(memo[isti[word][i]]) continue;
		dfs(isti[word][i], number);
	}
}

int main ()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	for(int i = 0; i < n; ++i) {
		cin >> a[i];
		if(not isNumber(a[i])) 
			c[a[i]].pb(i);
	}
	for(int i = 0; i < n; ++i) {
		cin >> b[i];
		if(not isNumber(b[i]))
			d[b[i]].pb(i);
	}
	
	for(int i = 0; i < n; ++i) {
		isti[a[i]].pb(b[i]);
		isti[b[i]].pb(a[i]);
	}
	
	for(int i = 0; i < n; ++i) {
		if(not memo[a[i]] and isNumber(a[i])) {
			dfs(a[i], a[i]);
			if(!ok)
				return cout << "NE", 0;
		}
		if(not memo[b[i]] and isNumber(b[i])) {
			dfs(b[i], b[i]);
			if(!ok)
				return cout << "NE", 0;
		}
	}
	
	cout << "DA";

return 0;
}

Compilation message

zamjena.cpp: In function 'void dfs(std::__cxx11::string, std::__cxx11::string)':
zamjena.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < isti[word].size(); ++i) {
                 ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 6 ms 3584 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 6 ms 3456 KB Output is correct
5 Correct 5 ms 3456 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3456 KB Output is correct
2 Correct 5 ms 3456 KB Output is correct
3 Correct 7 ms 3456 KB Output is correct
4 Correct 5 ms 3584 KB Output is correct
5 Correct 5 ms 3456 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 6 ms 3456 KB Output is correct
5 Correct 7 ms 3456 KB Output is correct
6 Correct 6 ms 3456 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3840 KB Output is correct
2 Correct 8 ms 3712 KB Output is correct
3 Correct 16 ms 4480 KB Output is correct
4 Correct 13 ms 4576 KB Output is correct
5 Correct 20 ms 4736 KB Output is correct
6 Correct 16 ms 4352 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6988 KB Output is correct
2 Correct 140 ms 10620 KB Output is correct
3 Correct 146 ms 14328 KB Output is correct
4 Correct 191 ms 15928 KB Output is correct
5 Correct 523 ms 24184 KB Output is correct
6 Correct 343 ms 17016 KB Output is correct