oj.uz

Submission #758034

# Submission time Handle Problem Language Result Execution time Memory
758034 2023-06-14T05:25:58 Z jer033 Grapevine (NOI22_grapevine) C++17
6 / 100
 52 ms 16964 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 8404 KB Output is correct
2 Correct 44 ms 8112 KB Output is correct
3 Correct 49 ms 8404 KB Output is correct
4 Correct 47 ms 8276 KB Output is correct
5 Correct 41 ms 8148 KB Output is correct
6 Correct 52 ms 8416 KB Output is correct
7 Correct 25 ms 8164 KB Output is correct
8 Correct 24 ms 8148 KB Output is correct
9 Correct 27 ms 8420 KB Output is correct
10 Correct 48 ms 8276 KB Output is correct
11 Correct 44 ms 8148 KB Output is correct
12 Correct 49 ms 8072 KB Output is correct
13 Correct 26 ms 8404 KB Output is correct
14 Correct 24 ms 8216 KB Output is correct
15 Correct 25 ms 8268 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 16964 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 412 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 8404 KB Output is correct
2 Correct 44 ms 8112 KB Output is correct
3 Correct 49 ms 8404 KB Output is correct
4 Correct 47 ms 8276 KB Output is correct
5 Correct 41 ms 8148 KB Output is correct
6 Correct 52 ms 8416 KB Output is correct
7 Correct 25 ms 8164 KB Output is correct
8 Correct 24 ms 8148 KB Output is correct
9 Correct 27 ms 8420 KB Output is correct
10 Correct 48 ms 8276 KB Output is correct
11 Correct 44 ms 8148 KB Output is correct
12 Correct 49 ms 8072 KB Output is correct
13 Correct 26 ms 8404 KB Output is correct
14 Correct 24 ms 8216 KB Output is correct
15 Correct 25 ms 8268 KB Output is correct
16 Runtime error 1 ms 340 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -