oj.uz

Submission #410584

# Submission time Handle Problem Language Result Execution time Memory
410584 2021-05-23T05:06:22 Z super_j6 Viruses (BOI20_viruses) C++14
0 / 100
 6 ms 8652 KB 
#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<int, 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];
int 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[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()){
		int 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++){
		int ret = *min_element(f[i][0], f[i][0] + w);
		if(ret < 0x3f3f3f3f) cout << "NO " << ret << endl;
		else cout << "YES" << endl;
	}
	
	return 0;
}

Compilation message

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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8652 KB Output is correct
2 Correct 5 ms 8652 KB Output is correct
3 Incorrect 5 ms 8652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8652 KB Output is correct
2 Correct 5 ms 8652 KB Output is correct
3 Correct 6 ms 8652 KB Output is correct
4 Correct 6 ms 8652 KB Output is correct
5 Incorrect 6 ms 8652 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8652 KB Output is correct
2 Correct 6 ms 8652 KB Output is correct
3 Incorrect 6 ms 8652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8652 KB Output is correct
2 Correct 5 ms 8652 KB Output is correct
3 Incorrect 5 ms 8652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8652 KB Output is correct
2 Correct 5 ms 8652 KB Output is correct
3 Incorrect 5 ms 8652 KB Output isn't correct
4 Halted 0 ms 0 KB -