Submission #410587

#	Time	Username	Problem	Language	Result	Execution time	Memory
410587		super_j6	Viruses (BOI20_viruses)	C++14	100 / 100	125 ms	19164 KiB

Viruses

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
#include <array>
#include <queue>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

typedef array<ll, 4> T;

const int mxn = 102;
int n, m, k, u = 1, w = 1;
int a[mxn], lk[mxn];
int b[mxn][mxn], g[mxn][mxn], tr[mxn][2];
ll f[mxn][mxn][mxn], dp[mxn][mxn][mxn];
queue<int> q;
priority_queue<T, vector<T>, greater<T>> pq;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> k;
	
	for(int i = 0; i < m; i++){
		int x, y, z = 0;
		cin >> x >> y;
		for(int j = 0; j < y; j++){
			int e;
			cin >> e;
			if(!g[z][e]) g[z][e] = u++;
			z = g[z][e];
		}
		b[z][x] = 1;
	}

	for(int i = 0; i < k; i++){
		int x, z = 0;
		cin >> x;
		for(int j = 0; j < x; j++){
			int y;
			cin >> y;
			if(!tr[z][y]) tr[z][y] = w++;
			z = tr[z][y];
		}
		a[z] = 1;
	}
	
	memset(f, 0x3f, sizeof(f));
	q.push(0);
	while(!q.empty()){
		int c = q.front();
		q.pop();
		for(int i = 0; i < 2; i++){
			int &x = tr[c][i], y = c ? tr[lk[c]][i] : 0;
			if(x) lk[x] = y, q.push(x);
			else x = y;
			if(!a[tr[0][i]] && !a[c] && !a[x]) f[i][c][x] = 1;
		}
	}
	
	memset(dp, 0x3f, sizeof(dp));
	for(int i = 0; i < w; i++) if(!a[i]) pq.push({dp[0][i][i] = 0, 0, i, i});
	
	while(!pq.empty()){
		ll c = pq.top()[1], x = pq.top()[2], y = pq.top()[3], d = pq.top()[0];
		pq.pop();
		if(d != dp[c][x][y]) continue;
		for(int i = 0; i < n; i++) if(b[c][i] && f[i][x][y] > d){
			f[i][x][y] = d;
			for(int j = 0, z; j < u; j++) if(z = g[j][i])
			for(int l = 0; l < w; l++){
				if(dp[z][l][y] > dp[j][l][x] + d){
					pq.push({dp[z][l][y] = dp[j][l][x] + d, z, l, y});
				}
			}
		} 
		for(int i = 0, z; i < n; i++) if(z = g[c][i])
		for(int j = 0; j < w; j++){
			if(dp[z][x][j] > d + f[i][y][j]){
				pq.push({dp[z][x][j] = d + f[i][y][j], z, x, j});
			}
		}
	}
	
	for(int i = 2; i < n; i++){
		ll ret = *min_element(f[i][0], f[i][0] + w);
		if(ret < 0x3f3f3f3f3f3f3f3f) cout << "NO " << ret << endl;
		else cout << "YES" << endl;
	}
	
	return 0;
}

Compilation message (stderr)

Viruses.cpp: In function 'int main()':
Viruses.cpp:77:39: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   77 |    for(int j = 0, z; j < u; j++) if(z = g[j][i])
      |                                     ~~^~~~~~~~~
Viruses.cpp:84:38: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   84 |   for(int i = 0, z; i < n; i++) if(z = g[c][i])
      |                                    ~~^~~~~~~~~

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