oj.uz

Submission #130954

# Submission time Handle Problem Language Result Execution time Memory
130954 2019-07-16T10:03:47 Z Lightning Zamjena (COCI18_zamjena) C++14
70 / 70
 128 ms 11256 KB 
#include <iostream>
#include <vector>
#include <set>
#include <map>

using namespace std;

typedef pair <int, bool> pib;

#define F first
#define S second
#define mkp make_pair
#define pb push_back
#define sz(a) (int)a.size()
#define show(x) cerr << "# " << #x << " = " << (x) << endl

const int N = 2e5;

int n, a[N], b[N], NUM = 1000;
bool va[N], vb[N], u[N];
vector <pib> g[N];
set <int> st;
map <string, int> num;

void dfs(int v, bool var) {
	u[v] = 1;
	if(!var) {
		st.insert(v);
	}
	for(pib it : g[v]) {
		int to = it.F;
		bool vto = it.S;
		if(!u[to]) {
			dfs(to, vto);
		}
	}
}

int main () {
	ios_base :: sync_with_stdio(false);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		string s;
		cin >> s;
		if('0' <= s[0] && s[0] <= '9') { // esli eto chislo
			a[i] = stoi(s);
		}
		else { // esli eto variable
			if(num[s] == 0) { // esli u nego netu nomera
				num[s] = ++NUM;			
			}
			a[i] = num[s];
			va[i] = 1;
		}
	}		
	for(int i = 1; i <= n; ++i) {
		string s;
		cin >> s;
		if('0' <= s[0] && s[0] <= '9') { // esli eto chislo
			b[i] = stoi(s);
		}
		else { // esli eto variable
			if(num[s] == 0) { // esli u nego netu nomera
				num[s] = ++NUM;			
			}
			b[i] = num[s];
			vb[i] = 1;
		}
	}
	// sozdaem graph
	for(int i = 1; i <= n; ++i) {
		g[a[i]].pb(mkp(b[i], vb[i]));
		g[b[i]].pb(mkp(a[i], va[i]));
	}
	// mutim dfs
	for(int i = 1; i <= n; ++i) {
		if(!u[a[i]]) {
			dfs(a[i], va[i]);
			if(sz(st) > 1) {
				cout << "NE";
				return 0;
			}
			st.clear();
		}
	}
	cout << "DA";
	return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5240 KB Output is correct
2 Correct 9 ms 5152 KB Output is correct
3 Correct 12 ms 5432 KB Output is correct
4 Correct 11 ms 5368 KB Output is correct
5 Correct 10 ms 5396 KB Output is correct
6 Correct 10 ms 5368 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6108 KB Output is correct
2 Correct 39 ms 7172 KB Output is correct
3 Correct 66 ms 8496 KB Output is correct
4 Correct 79 ms 9112 KB Output is correct
5 Correct 128 ms 11256 KB Output is correct
6 Correct 105 ms 9028 KB Output is correct