oj.uz

Submission #158563

# Submission time Handle Problem Language Result Execution time Memory
158563 2019-10-17T21:25:21 Z jvalsortav Zamjena (COCI18_zamjena) C++14
70 / 70
 357 ms 16220 KB 
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cctype>
#include <ctime>
#include <set>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <utility>
#include <string>
#include <map>
#include <iterator>
#define ll long long
#define mp make_pair

using namespace std;

const int M = 1000000007;

ll pot(ll A, ll B){
   ll R = 1;
   while (B){
		 if (B&1) R *= A;
		 R %= M;
		 A *= A; A %= M;
		 B >>= 1;
   }
   return R;
}

int n;
int c;
string s, h;
map <string, vector <string> > m;
vector <string> v[2];
map <string, int> vis;
bool inf = true;

void dfs(string node){
	if (vis[node]) return;
	/*cout << node << " " << c << "\n";*/
	if (isdigit(node[0])) c++;
	if (c >= 2) inf = false;
	if (inf == false) return;
	vis[node] = 1;
	
	for (int i = 0; i < m[node].size(); i++){
		dfs(m[node][i]);
	}
	return;
}

int main() {

	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n;
	
	for (int i = 0; i < 2*n; i++){
		cin >> s; v[i/n].push_back(s);
		vis[s] = 0;
	}
	
	for (int i = 0; i < n; i++){
		s = v[0][i]; h = v[1][i];
		m[s].push_back(h);
		m[h].push_back(s);
	}
	
	for (int i = 0; i < n; i++){
		c = 0; dfs(v[0][i]); 
		c = 0; dfs(v[1][i]);
		if (!inf) break;
	}
	
	if (inf) cout << "DA";
	else cout << "NE";
	
return 0;
}

Compilation message

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 9 ms 1144 KB Output is correct
4 Correct 11 ms 1400 KB Output is correct
5 Correct 14 ms 1400 KB Output is correct
6 Correct 11 ms 1272 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3252 KB Output is correct
2 Correct 91 ms 5932 KB Output is correct
3 Correct 91 ms 9504 KB Output is correct
4 Correct 148 ms 11728 KB Output is correct
5 Correct 357 ms 16220 KB Output is correct
6 Correct 227 ms 12496 KB Output is correct