Submission #802596

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
802596	2023-08-02T12:51:14 Z	parsadox2	Viruses (BOI20_viruses)	C++14	11 / 100	1 ms	360 KB

Viruses

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 1e2 + 10;
int n , g , m , w[maxn] , val[maxn] , st[maxn] , dis[maxn];
vector <int> ar[maxn];
vector <pair<int ,int>> adj[maxn];
bool marked[maxn];

void dij()
{
	priority_queue <pair<int ,int>> pq;
	memset(dis , 63 , sizeof dis);
	dis[0] = dis[1] = 1;
	pq.push({1 , 0});
	pq.push({1 , 1});
	while(!pq.empty())
	{
		auto now = pq.top();  pq.pop();
		int D = abs(now.first) , v = now.second;
		if(marked[v])
			continue;
		//cout << v << " " << D << endl;
		marked[v] = true;
		for(auto e : adj[v])
		{
			int u = e.first , ind = e.second;
			val[ind] += D;
			w[ind]--;
			//cout << ind << " " << w[ind] << endl;
			if(w[ind] == 0 && val[ind] < dis[u])
			{
				dis[u] = val[ind];
				pq.push({-dis[u] , u});
			}
		}
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> g >> n >> m;
	for(int i = 0 ; i < n ; i++)
	{
		int x;  cin >> st[i] >> x;
		w[i] = x;
		for(int j = 0 ; j < x ; j++)
		{
			int y;  cin >> y;
			ar[i].push_back(y);
			adj[y].push_back({st[i] , i});
		}
	}
	dij();
	for(int i = 0 ; i < m ; i++)
	{
		int x;  cin >> x;
		while(x--)
		{
			int y;  cin >>y;
		}
	}
	for(int i = 2 ; i < g ; i++)
	{
		if(!marked[i])
			cout << "YES" << endl;
		else
			cout << "NO " << dis[i] << endl;
	}
	return 0;
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	360 KB	Output is correct
2	Correct	1 ms	324 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	256 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	328 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	332 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	324 KB	Output is correct
17	Correct	1 ms	324 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	328 KB	Output is correct

Subtask #2

0 / 14.0

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

Subtask #3

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	360 KB	Output is correct
2	Correct	1 ms	324 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	256 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	328 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	332 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	324 KB	Output is correct
17	Correct	1 ms	324 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	328 KB	Output is correct
21	Incorrect	1 ms	320 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #5

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	360 KB	Output is correct
2	Correct	1 ms	324 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	256 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	328 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	332 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	324 KB	Output is correct
17	Correct	1 ms	324 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	328 KB	Output is correct
21	Incorrect	1 ms	212 KB	Output isn't correct
22	Halted	0 ms	0 KB	-