Submission #254798

#	Time	Username	Problem	Language	Result	Execution time	Memory
254798		model_code	Viruses (BOI20_viruses)	C++17	100 / 100	89 ms	2688 KiB

Viruses

#include <bits/stdc++.h>
using namespace std;
#define MAXG 305
#define MAXL 55
#define MYINFLL 1000000000000000000LL

#define V(args...) (vector<int>({args}))

static long long a[MAXG][MAXL][MAXL];
static set<pair<long long, pair<int, pair<int, int>>>> q;

void update(int i, int st, int en, long long val) {
	if (val < a[i][st][en]) {
		set<pair<long long, pair<int, pair<int, int>>>>::iterator it = q.find(make_pair(a[i][st][en], make_pair(i, make_pair(st, en))));
		if (it != q.end()) {
			q.erase(it);
		}
		a[i][st][en] = val;
		q.insert(make_pair(val, make_pair(i, make_pair(st, en))));
	}
}

int main() {
	int G, N, M;
	scanf("%d %d %d",&G,&N,&M);
	int origG = G;

	vector<pair<int, vector<int>>> mutations;

	for (int i = 0; i < N; i++) {
		int startGene, len;
		scanf("%d %d", &startGene, &len);

		if (len == 1) {
			int endGene;
			scanf("%d", &endGene);
			mutations.push_back(make_pair(startGene, V(endGene)));
		} else {
			int cur = startGene;
			while (1) {
				int nextGene;
				scanf("%d", &nextGene);
				len--;
				if (len == 1) {
					int finalGene;
					scanf("%d", &finalGene);
					mutations.push_back(make_pair(cur, V(nextGene, finalGene)));
					break;
				}
				mutations.push_back(make_pair(cur, V(nextGene, G)));
				cur = G;
				G++;
			}
		}
	}

	vector<int> mutationsByRhs[MAXG];
	for (int ind = 0; ind < (int) mutations.size(); ind++) {
		vector<int> rhs = mutations[ind].second;
		if ((rhs.size() == 1) || ((rhs.size() == 2) && (rhs[0] == rhs[1]))) {
			mutationsByRhs[rhs[0]].push_back(ind);
		} else {
			mutationsByRhs[rhs[0]].push_back(ind);
			mutationsByRhs[rhs[1]].push_back(ind);
		}
	}

	set<string> keywords;
	set<string> prefixesSet;
	prefixesSet.insert("");

	for (int i = 0; i < M; i++) {
		int len;
		scanf("%d", &len);
		string s = "";
		for (int j = 0; j < len; j++) {
			int elem;
			scanf("%d", &elem);
			s += elem ? "1" : "0";
		}
		keywords.insert(s);
		for (int j = 1; j <= len; j++) {
			prefixesSet.insert(s.substr(0, j));
		}
	}

	vector<pair<string, bool>> prefixes;
	map<string, int> indexes;
	for (string prefix : prefixesSet) {
		bool isTerminal = false;
		for (int i = 0; i < prefix.size(); i++) {
			set<string>::iterator it = keywords.find(prefix.substr(i));
			if (it != keywords.end()) {
				isTerminal = true;
			}
		}
		indexes.insert(make_pair(prefix, (int) prefixes.size()));
		prefixes.push_back(make_pair(prefix, isTerminal));
	}

	int S = (int) prefixes.size();

	for (int i = 0; i < G; i++) {
		for (int st = 0; st < S; st++) {
			for (int en = 0; en < S; en++) {
				a[i][st][en] = MYINFLL;
			}
		}
	}

	for (int st = 0; st < S; st++) {
		if (!prefixes[st].second) {
			for (int i = 0; i < 2; i++) {
				string s = prefixes[st].first + (i == 0 ? "0" : "1");
				while (prefixesSet.find(s) == prefixesSet.end()) {
					s = s.substr(1, s.size() - 1);
				}
				int en = indexes[s];
				if (!prefixes[en].second) {
					update(i, st, en, 1LL);
				}
			}
		}
	}

	while (q.size() > 0) {
		set<pair<long long, pair<int, pair<int, int>>>>::iterator current = q.begin();
		int i = current->second.first;
		int st = current->second.second.first;
		int en = current->second.second.second;
		q.erase(current);

		for (int ind : mutationsByRhs[i]) {
			pair<int, vector<int>> mutation = mutations[ind];
			if (mutation.second.size() == 1) {
				update(mutation.first, st, en, a[i][st][en]);
			} else {
				if (mutation.second[0] == i) {
					for (int md = 0; md < S; md++) {
						update(mutation.first, st, md, a[i][st][en] + a[mutation.second[1]][en][md]);
					}
				}
				if (mutation.second[1] == i) {
					for (int md = 0; md < S; md++) {
						update(mutation.first, md, en, a[mutation.second[0]][md][st] + a[i][st][en]);
					}
				}
			}
		}
	}

	for (int i = 2; i < origG; i++) {
		long long res = MYINFLL;
		for (int en = 0; en < S; en++) {
			if (a[i][0][en] < res) {
				res = a[i][0][en];
			}
		}
		if (res == MYINFLL) {
			printf("YES\n");
		} else {
			printf("NO %lli\n", res);
		}
	}

	return 0;
}

Compilation message (stderr)

Viruses.cpp: In function 'int main()':
Viruses.cpp:91:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < prefix.size(); i++) {
                   ~~^~~~~~~~~~~~~~~
Viruses.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&G,&N,&M);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
Viruses.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &startGene, &len);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Viruses.cpp:36:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &endGene);
    ~~~~~^~~~~~~~~~~~~~~~
Viruses.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &nextGene);
     ~~~~~^~~~~~~~~~~~~~~~~
Viruses.cpp:46:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d", &finalGene);
      ~~~~~^~~~~~~~~~~~~~~~~~
Viruses.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &len);
   ~~~~~^~~~~~~~~~~~
Viruses.cpp:78:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &elem);
    ~~~~~^~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 32 / 32
• Subtask 5: 18 / 18