| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1106349 |
2024-10-30T04:12:14 Z |
Requiem |
Viruses (BOI20_viruses) |
C++17 |
|
2 ms |
8952 KB |
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "Viruses"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
/**
Tóm tắt đề:
- Cho G gene, đánh số từ 0 đến G - 1.
- Cho N thao tác đột biến
Từ gene có chỉ số a, nó sẽ tạo thành 1 chuỗi gene mới có độ dài k x1 x2 x3 ... xk
Ta có M kháng thể ở dạng nhị phân.
VỚi từng số a từ 2 đến G - 1, ta muốn đột biến a cho đến khi:
- a trở thành 1 chuỗi nhị phân
- không chứa 1 chuỗi kháng thể nào.
Với những thằng biến đổi được thì xuất độ dài ngắn nhất
Ngược lại, xuất NO.
Sol chuẩn:
subtask 1 (M = 1):
Bài này ta sẽ giải bằng dijkstra / dp đại loại thế.
Ta xuất phát từ thằng x mà chưa được giải xong ta cập nhật 1 thằng bố của nó.
subtask 3 (M = 1):
Bây giờ có nhiều gene được tạo thành từ 1 con virus nên ta
cần phải decode nó thành 1 trạng thái.
dp_i_st_en: Số thằng đột biến từ gen i, xuất phát ở trạng thái st,
và kết thúc ở trạng thái en.
Giả sử ta có thao tác biến a --> <b1, b2, ..., bk>
dp_a_st_en = dp_b1_st_x1 + dp_b2_x1_x2 + dp_b3_x2_x3 + ... + dp_bk_xk-1_en.
Ta biến đổi như sau: 1 thao tác a --> <b1, b2, ..., bk> có thể
được biến đổi thành a --> <b1, z>
z là 1 gen mới và có khả năng z --> <b2, b3, ..., bk>
Trong trường hợp tệ nhất, số gene vẫn là O(G).
Bây giờ ta có thể chuyển trạng thái mượt mà hơn nhờ vào cái này.
a --> <b1>:
dp_i_st_en = min(dp_i_st_en, dp_b1_st_en).
a --> <b1, b2>:
dp_i_st_en = min(dp_i_st_en, di_b1_st_x1 + dp_b2_x1_en)
Nếu ta imple được cái thuật này thì độ phức tạp của nó sẽ là:
- Ta có O(S^2 * G) trạng thái
- Để chuyển trạng thái cho thằng kia, ta cần thêm 1 vòng for S nữa nên độ phức tạp là:
O(S^3 * G * log2(G * S^2)) nếu ta dijkstra.
Thế cái state ở đây là gì: state ở đây là độ khớp với 1 prefix của thằng kháng nguyên,
tức là ta muốn biết là ở độ khớp hiện tại.
Ta gọi dp_i_st_en: độ dài tối thiểu của con virus sao cho nó bắt đầu ở trạng thái khớp
tiền tố st của thằng antibody và kết thúc ở trạng thái khớp tiền tố độ dài l của thằng antibody.
**/
const int MAXN = 301;
int numGene = 0;
int numMutation = 0;
int numAntibody = 0;
int head[MAXN];
vector<int> mutation[MAXN];
vector<int> origin[MAXN];
string antibody[MAXN];
namespace subtask1{
bool check(){
return numAntibody == 0;
}
unsigned long long dp[MAXN];
void solve(){
FOR(i, 1, numMutation){
for(auto p: mutation[i]){
origin[p].pb(i);
}
}
memset(dp, 0x3f, sizeof(dp));
dp[1] = 1;
dp[0] = 1;
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push({1, 1});
pq.push({1, 0});
while(!pq.empty()){
int du = pq.top().fi;
int u = pq.top().se;
pq.pop();
if (du > dp[u]) continue;
for(auto id: origin[u]){
int a = head[id];
int cur = 0;
for(auto b: mutation[id]){
cur += dp[b];
}
if (minimize(dp[a], (ull) cur)){
pq.push({dp[a], a});
}
}
}
FOR(i, 2, numGene - 1){
if (dp[i] < inf) cout << dp[i] << endl;
else cout << "0" << endl;
}
}
}
namespace subtask3{
bool check(){
return numAntibody == 1;
}
ull dp[MAXN][51][51];
int lps[MAXN], automata[MAXN][2];
struct state{
int id, st, en;
int val;
state(int _val = 0, int _id = 0, int _st = 0, int _en = 0){
val = _val, st = _st, en = _en, id = _id;
}
bool operator < (const state &other) const {
return val < other.val;
}
};
void buildKMP(){
int len = antibody[1].length();
string anti = antibody[1];
anti = '#' + anti + '#';
FOR(i, 2, len){
int j = lps[i - 1];
while(j > 0 and anti[j + 1] != anti[i]) j = lps[j];
if (anti[j + 1] == anti[i]) lps[i] = j + 1;
}
FOR(i, 0, len){
FOR(c, 0, 1){
if (anti[i + 1] - '0' == c) automata[i][c] = i + 1;
else automata[i][c] = automata[lps[i]][c];
}
}
}
void solve(){
set<pair<ii, ii>> pq;
memset(dp, 0x3f, sizeof(dp));
buildKMP();
int tmp = numGene;
FOR(i, 1, numMutation){
while(mutation[i].size() > 2){
int x2 = mutation[i].back();
mutation[i].pop_back();
int x1 = mutation[i].back();
mutation[i].pop_back();
mutation[++numMutation].pb(x1);
mutation[numMutation].pb(x2);
head[numMutation] = ++numGene;
mutation[i].pb(numGene);
}
}
FOR(i, 1, numMutation){
for(int j = 0; j < mutation[i].size(); j++){
origin[mutation[i][j]].pb(i);
}
}
FOR(i, 0, 1){
FOR(st, 0, antibody[1].length() - 1){
int en = automata[st][i];
if (en < antibody[1].length()) {
dp[i][st][en] = 1;
pq.insert({{1, i}, {st, en}});
}
}
}
int complexity = 0;
while(!pq.empty()){
pair<ii, ii> tp = *pq.begin();
int u = tp.fi.se;
int st = tp.se.fi;
int en = tp.se.se;
int du = tp.fi.fi;
pq.erase(pq.begin());
if (du > dp[u][st][en]) continue;
complexity++;
for(auto id: origin[u]){
int a = head[id];
if (mutation[id].size() == 1){
if (minimize(dp[a][st][en],(ull) du))
pq.insert({{du, a}, {st, en}});
}
else{
int other = ((mutation[id][0] == u) ? mutation[id][1] : mutation[id][0]);
FOR(third, 0, antibody[1].length() - 1){
if (mutation[id][0] == u) {
if (minimize(dp[a][st][third],(ull) du + dp[other][en][third])){
if (pq.find({{dp[a][st][third], a}, {st, third}}) == pq.end())
pq.insert({{dp[a][st][third], a}, {st, third}});
}
}
if (mutation[id][1] == u){
if (minimize(dp[a][third][en], (ull) dp[other][third][st] + du)){
if (pq.find({{dp[a][third][en], a}, {third, en}}) == pq.end())
pq.insert({{dp[a][third][en], a}, {third, en}});
}
}
}
}
}
}
FOR(i, 2, tmp - 1){
ull ans = inf + 1;
FOR(j, 0, (int) antibody[1].length() - 1){
minimize(ans, dp[i][0][j]);
}
if (ans < inf) cout << ans << endl;
else cout << "0\n";
}
}
}
namespace subtask5{
bool check(){
return true;
}
struct TrieNode{
int child[2], suffixLink, depth, parent, bad;
int automata[2];
TrieNode(){
suffixLink = 0;
parent = 0;
depth = 0;
bad = false;
memset(child, 0, sizeof(child));
memset(automata, 0, sizeof(automata));
}
};
struct Trie{
vector<TrieNode> T = {TrieNode()};
void addNum(string str){
int p = 0;
for(int i = 0; i < (int) str.length(); i++){
int c = str[i] - '0';
if (T[p].child[c] == 0){
T[p].child[c] = T.size();
T.pb(TrieNode());
}
T[T[p].child[c]].depth = T[p].depth + 1;
T[T[p].child[c]].parent = p;
p = T[p].child[c];
}
T[p].bad = true;
}
void constructAC(){
queue<ii> q;
q.push({0, -1});
while(!q.empty()){
int u = q.front().fi;
int c = q.front().se;
q.pop();
if (T[u].depth <= 1) {
T[u].suffixLink = 0;
}
else{
int prv = T[T[u].parent].suffixLink;
while(prv > 0 and T[prv].child[c] == 0){
prv = T[prv].suffixLink;
}
if (T[prv].child[c] != 0) T[u].suffixLink = T[prv].child[c];
}
T[u].automata[0] = ((T[u].child[0] > 0) ? (T[u].child[0]) : (T[T[u].suffixLink].automata[0]));
T[u].automata[1] = ((T[u].child[1] > 0) ? (T[u].child[1]) : (T[T[u].suffixLink].automata[1]));
T[u].bad |= T[T[u].parent].bad;
T[u].bad |= T[T[u].suffixLink].bad; //1 tien to la te khi ma chua 1 tien to khac le te.
for(int i = 0; i < 2; i++){
if (T[u].child[i] > 0) q.push({T[u].child[i], i});
}
}
}
};
ull dp[MAXN][59][59];
void solve(){
Trie Trie;
FOR(i, 1, numAntibody){
Trie.addNum(antibody[i]);
}
Trie.constructAC();
int tmp = numGene;
FOR(i, 1, numMutation){
while(mutation[i].size() > 2){
int x2 = mutation[i].back();
mutation[i].pop_back();
int x1 = mutation[i].back();
mutation[i].pop_back();
mutation[++numMutation].pb(x1);
mutation[numMutation].pb(x2);
head[numMutation] = ++numGene;
mutation[i].pb(numGene);
}
}
FOR(i, 1, numMutation){
FOR(j, 0, (int) mutation[i].size() - 1){
origin[mutation[i][j]].pb(i);
}
}
memset(dp, 0x3f, sizeof(dp));
priority_queue<pair<ii, ii>, vector<pair<ii, ii>>, greater<pair<ii, ii>>> pq;
FOR(i, 0, 1){
FOR(j, 0, (int) Trie.T.size() - 1){
if (Trie.T[j].bad) continue;
int st = j;
int en = Trie.T[j].automata[i];
if (Trie.T[en].bad) continue;
pq.push({{1,i} , {st,en}});
dp[i][st][en] = 1;
}
}
while(!pq.empty()){
pair<ii, ii> tp = pq.top();
int u = tp.fi.se;
int st = tp.se.fi;
int en = tp.se.se;
int du = tp.fi.fi;
pq.pop();
if (du > dp[u][st][en]) continue;
for(auto id: origin[u]){
int a = head[id];
if (mutation[id].size() == 1){
if (minimize(dp[a][st][en], (ull) du)){
pq.push({{dp[a][st][en], a}, {st, en}});
}
}
else {
int other = ((mutation[id][0] == u) ? mutation[id][1] : mutation[id][0]);
FOR(third, 0, Trie.T.size() - 1){
if (mutation[id][0] == u){
if (minimize(dp[a][st][third], (ull) du + dp[other][en][third])){
pq.push({ {dp[a][st][third], a} , {st, third} });
}
}
if (mutation[id][1] == u){
if (minimize(dp[a][third][en], (ull) dp[other][third][st] + du)){
pq.push({ {dp[a][third][en], a}, {third, en} });
}
}
}
}
}
}
FOR(i, 2, tmp - 1){
ull ans = inf;
FOR(j, 0, (int) Trie.T.size() - 1){
minimize(ans, dp[i][0][j]);
}
if (ans < inf) cout << ans << endl;
else cout << 0 << endl;
}
}
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin >> numGene >> numMutation >> numAntibody;
FOR(i, 1, numMutation){
int a;
int k;
cin >> a >> k;
head[i] = a;
FOR(j, 0, k - 1){
int x;
cin >> x;
mutation[i].pb(x);
}
}
FOR(i, 1, numAntibody){
int x;
cin >> x;
FOR(j, 0, x - 1){
char c;
cin >> c;
antibody[i] = antibody[i] + c;
}
}
// if (subtask1::check()) return subtask1::solve(), 0;
// if (subtask3::check()) return subtask3::solve(), 0;
if (subtask5::check()) return subtask5::solve(), 0;
}
/**
Warning:
Đọc sai đề???
Cận lmao
Code imple thiếu case nào không.
Limit.
**/
Compilation message
Viruses.cpp: In function 'void subtask1::solve()':
Viruses.cpp:115:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
115 | if (du > dp[u]) continue;
| ~~~^~~~~~~
Viruses.cpp: In function 'void subtask3::solve()':
Viruses.cpp:198:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
198 | for(int j = 0; j < mutation[i].size(); j++){
| ~~^~~~~~~~~~~~~~~~~~~~
Viruses.cpp:10:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
......
204 | FOR(st, 0, antibody[1].length() - 1){
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Viruses.cpp:204:13: note: in expansion of macro 'FOR'
204 | FOR(st, 0, antibody[1].length() - 1){
| ^~~
Viruses.cpp:206:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
206 | if (en < antibody[1].length()) {
| ~~~^~~~~~~~~~~~~~~~~~~~~~
Viruses.cpp:223:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
223 | if (du > dp[u][st][en]) continue;
| ~~~^~~~~~~~~~~~~~~
Viruses.cpp:10:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
......
234 | FOR(third, 0, antibody[1].length() - 1){
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Viruses.cpp:234:21: note: in expansion of macro 'FOR'
234 | FOR(third, 0, antibody[1].length() - 1){
| ^~~
Viruses.cpp: In function 'void subtask5::solve()':
Viruses.cpp:391:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
391 | if (du > dp[u][st][en]) continue;
| ~~~^~~~~~~~~~~~~~~
Viruses.cpp:10:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<subtask5::TrieNode>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
......
404 | FOR(third, 0, Trie.T.size() - 1){
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~
Viruses.cpp:404:22: note: in expansion of macro 'FOR'
404 | FOR(third, 0, Trie.T.size() - 1){
| ^~~
Viruses.cpp: At global scope:
Viruses.cpp:435:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
435 | main()
| ^~~~
Viruses.cpp: In function 'int main()':
Viruses.cpp:439:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
439 | freopen(TASKNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Viruses.cpp:440:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
440 | freopen(TASKNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
