Submission #758034

#	Time	Username	Problem	Language	Result	Execution time	Memory
758034		jer033	Grapevine (NOI22_grapevine)	C++17	6 / 100	52 ms	16964 KiB

Main

#include <algorithm>
#include <iostream>

int tree[2005][2005][2];
long long edgews[2005];
int grape[2005];
int bfs[2005];
int visited[2005];
long long dist[2005];//arrays that will be used in the solve function

using namespace std;

long long solve(int n, int qj, int tree[2005][2005][2], long long edgews[2005], int grape[2005], int bfs[2005], int visited[2005], long long dist[2005])
{
	for (int i=0; i<=n+1; i++)
	{
		bfs[i]=0;
		visited[i]=0;
		dist[i]=0;//just to be sure
	}
	bfs[1]=qj;
	dist[1]=0;
	visited[qj]=1;
	int explored=0;
	int seen=1;
	while (explored<n)//i want to explore all nodes
	{
		explored++;
		int node=bfs[explored];
		int edgecount=tree[node][0][0];
		for (int i=1; i<=edgecount; i++)
		{
			int newnode=tree[node][i][0];
			if (1-visited[newnode])
			{
				seen++;
				bfs[seen]=newnode;
				visited[newnode]=1;
				dist[seen]=dist[explored]+edgews[tree[node][i][1]];
			}
		}
	}
	long long best = 1000000000000000000;
	for (int i=1; i<=n; i++)
	{
		if (grape[bfs[i]])
		{
			best=min(best, dist[i]);
		}
	}
	if (best==1000000000000000000)
	{
		return -1;
	}
	return best;
}

int main()
{
	int n, q;
	cin >> n >> q;
	for (int i=1; i<=n-1; i++)
	{
		int a, b;
		long long wei;
		cin >> a >> b >> wei;
		tree[a][0][0]++;
		tree[a][tree[a][0][0]][0]=b;
		tree[a][tree[a][0][0]][1]=i;
		tree[b][0][0]++;
		tree[b][tree[b][0][0]][0]=a;
		tree[b][tree[b][0][0]][1]=i;
		edgews[i]=wei;
	}
	for (int query=1; query<=q; query++)
	{
		int typ;
		cin >> typ;
		if (typ==1)
		{
			int qj;
			cin >> qj;
			cout << solve(n, qj, tree, edgews, grape, bfs, visited, dist) << '\n';
			//O(n) operation
		}
		else if (typ==2)
		{
			int ui;
			cin >> ui;
			grape[ui]=1-grape[ui];
			//O(1) operation
		}
		else
		{
			int ai, bi;
			long long weig;
			cin >> ai >> bi >> weig;
			int ind=1;
			while (tree[ai][ind][0]!=bi)
			{
				ind++;
			}
			edgews[tree[ai][ind][1]]=weig;
			//O(n) operation
		}
	}
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 18
• Subtask 6: 0 / 32