Submission #1290191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290191		muhammad-ahmad	Grapevine (NOI22_grapevine)	C++20	6 / 100	36 ms	13728 KiB

Main

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
#include <chrono>
using namespace std;

#define int long long
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second

const int N = 2005;
bool G[N];
int dist[N], MAT[N][N];
vector<int> adj[N];

int bfs(int S){
	for (int i = 1; i < N; i++) dist[i] = 1e18;
	dist[S] = 0;
	queue<int> Q;
	Q.push(S);
	while (Q.size()){
		int u = Q.front(); Q.pop();
		for (auto v : adj[u]){
			if (dist[v] > dist[u] + MAT[u][v]){
				dist[v] = dist[u] + MAT[u][v];
				Q.push(v);
			}
		}
	}
	
	int ans = 1e18;
	for (int i = 1; i < N; i++){
		if (G[i]) ans = min(ans, dist[i]);
	}
	if (ans == 1e18) return -1;
	return ans;
}

void solve() {
	int n, q; cin >> n >> q;
	for (int i = 1; i < n; i++){
		int a, b, w;
		cin >> a >> b >> w;
		MAT[a][b] = w;
		MAT[b][a] = w;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	for (int i = 1; i <= q; i++){
		int t; cin >> t;
		if (t == 1){
			int Q; cin >> Q;
			cout << bfs(Q) << endl;
		}
		else if (t == 2){
			int Q; cin >> Q;
			G[Q] ^= 1;
		}
		else {
			int a, b, w; cin >> a >> b >> w;
			MAT[a][b] = w;
			MAT[b][a] = w;
		}
	}
	
	return;
}

signed main() {
    // fast_io();
    srand(chrono::steady_clock::now().time_since_epoch().count());
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
    return 0;
}

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