Submission #802596

#	Time	Username	Problem	Language	Result	Execution time	Memory
802596		parsadox2	Viruses (BOI20_viruses)	C++14	11 / 100	1 ms	360 KiB

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 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 32
• Subtask 5: 0 / 18