Submission #378303

#	Time	Username	Problem	Language	Result	Execution time	Memory
378303		AriaH	Viruses (BOI20_viruses)	C++11	43 / 100	798 ms	262148 KiB

Viruses

/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define node						pair < int, pii >
#define I1							F
#define I2							S.F
#define I3							S.S

const int N = 110;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 1e18;
const int LOG = 22;
const int sigma = 2;
const int M = 51;
const int N2 = 65e4;

int ptr, ptr2, mp[N][N], MP[2 * N][M][M];

inline int id(int a, int b)
{
	if(mp[a][b] == 0)
	{
		mp[a][b] = ++ ptr;
	}
	return mp[a][b];
}

inline int state(int a, int b, int c, int d)
{
	a = id(a, b);
	if(MP[a][c][d] == 0)
	{
		MP[a][c][d] = ++ptr2;
	}
	return MP[a][c][d];
}

bool mark[N2];

int G, n, m, ts, sz[N], a[N], b[N][M], nxt[sigma][N], F[N], Q[N], Bad[N];

ll dp[N2], Ans[N]; /// dp[i][j][v][u] -> i omin equation andise j om ba rase avalie shoro v, rase kononi u be tori ke Bad nadide bashim -> min tool chie

vector < int > equ[N];

set < pair < ll, int > > st;

vector < pii > UPD[N2];

void build_aho()
{
	int l = 0, r = 0;
	for(int i = 0; i < sigma; i ++)
	{
		if(nxt[i][0]) Q[r ++] = nxt[i][0];
	}
	while(l < r)
	{
		int v = Q[l ++];
		Bad[v] |= Bad[F[v]];
		for(int i = 0; i < sigma; i ++)
		{
			if(nxt[i][v] == 0)
			{
				nxt[i][v] = nxt[i][F[v]];
			}
			else
			{
				F[nxt[i][v]] = nxt[i][F[v]];
				Q[r ++] = nxt[i][v];
			}
		}
	}
}

int main()
{
	scanf("%d%d%d", &G, &n, &m);
	for(int i = 1; i <= n; i ++)
	{
		scanf("%d%d", &a[i], &sz[i]);
		equ[a[i]].push_back(i);
		for(int j = 1; j <= sz[i]; j ++)
		{
			scanf("%d", &b[i][j]);
		}
	}
	equ[0].push_back(n + 1);
	equ[1].push_back(n + 2);
	for(int i = 1; i <= m; i ++)
	{
		int T;
		scanf("%d", &T);
		int v = 0;
		for(int j = 1; j <= T; j ++)
		{
			int x;
			scanf("%d", &x);
			if(!nxt[x][v]) nxt[x][v] = ++ts;
			v = nxt[x][v];
		}
		Bad[v] = 1;
	}
	build_aho();
	for(int v = 0; v <= ts; v ++)
	{
		for(int i = 1; i <= n + 2; i ++)
		{
			for(int j = 0; j < sz[i]; j ++)
			{
				for(int u = 0; u <= ts; u ++)
				{
					for(int z = 0; z <= ts; z ++)
					{
						if(Bad[v] || Bad[u] || Bad[z]) continue;
						int to = state(i, j + 1, v, z), from1 = state(i, j, v, u);
						for(auto now : equ[b[i][j + 1]])
						{
							int from2 = state(now, sz[now], u, z);
							UPD[from1].push_back(Mp(to, from2));
							UPD[from2].push_back(Mp(to, from1));
						}
					}
				}
			}
		}
	}
	for(int i = 0; i < N2; i ++) dp[i] = inf;
	for(int i = 1; i <= n; i ++)
	{
		for(int v = 0; v <= ts; v ++)
		{
			if(Bad[v]) continue;
			dp[state(i, 0, v, v)] = 0;
			st.insert({0, state(i, 0, v, v)});
		}
	}
	for(int i = 0; i <= ts; i ++)
	{
		if(Bad[i]) continue;
		if(!Bad[nxt[0][i]]) dp[state(n + 1, 0, i, nxt[0][i])] = 1, st.insert({1, state(n + 1, 0, i, nxt[0][i])});
		if(!Bad[nxt[1][i]]) dp[state(n + 2, 0, i, nxt[1][i])] = 1, st.insert({1, state(n + 2, 0, i, nxt[1][i])});
	}
	while(!st.empty())
	{
		int cu = st.begin()->S;
		ll cost = st.begin()->F;
		st.erase(st.begin());
		if(mark[cu]) continue;
		mark[cu] = 1;
		for(auto x : UPD[cu])
		{
			int fir = x.F, sec = x.S;
			if(dp[fir] > cost + dp[sec])
			{
				dp[fir] = cost + dp[sec];
				st.insert(Mp(dp[fir], fir));
			}
		}
	}
	for(int i = 0; i < N; i ++) Ans[i] = inf;
	for(int i = 1; i <= n; i ++)
	{
		ll mn = inf;
		for(int v = 0; v <= ts; v ++)
		{
			if(Bad[v]) continue;
			mn = min(mn, dp[state(i, sz[i], 0, v)]);
		}
		Ans[a[i]] = min(Ans[a[i]], mn);
	}
	for(int i = 2; i < G; i ++)
	{
		if(Ans[i] == inf)
		{
			printf("YES\n");
		}
		else
		{
			printf("NO %lld\n", Ans[i]);
		}
	}
	return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

Viruses.cpp: In function 'int main()':
Viruses.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |  scanf("%d%d%d", &G, &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Viruses.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |   scanf("%d%d", &a[i], &sz[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Viruses.cpp:100:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |    scanf("%d", &b[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~
Viruses.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |   scanf("%d", &T);
      |   ~~~~~^~~~~~~~~~
Viruses.cpp:113:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  113 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~

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