Submission #1113249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113249		fern	Grapevine (NOI22_grapevine)	C++17	0 / 100	2099 ms	12788 KiB

Main

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

const int INF = 1e9 + 7;

struct Edge {
    int to, weight, id;
};

struct Query {
    int type, x, y, z;
};

vector<vector<Edge>> adj;
vector<int> grapes;
vector<bool> hasGrape;

int n, q;

// Dijkstra's Algorithm for shortest path to nearest grape
vector<int> dijkstra() {
    vector<int> dist(n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

    for (int grape : grapes) {
        dist[grape] = 0;
        pq.emplace(0, grape);
    }

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;

        for (auto [v, weight, _] : adj[u]) {
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.emplace(dist[v], v);
            }
        }
    }

    return dist;
}

// Update edge weights
void updateEdge(int a, int b, int w) {
    for (auto &edge : adj[a]) {
        if (edge.to == b) {
            edge.weight = w;
            break;
        }
    }
    for (auto &edge : adj[b]) {
        if (edge.to == a) {
            edge.weight = w;
            break;
        }
    }
}

// Process queries
void processQueries(vector<Query> &queries) {
    for (auto &query : queries) {
        if (query.type == 1) {
            int qi = query.x;
            auto dist = dijkstra();
            cout << (dist[qi] == INF ? -1 : dist[qi]) << "\n";
        } else if (query.type == 2) {
            int ui = query.x;
            if (hasGrape[ui]) {
                hasGrape[ui] = false;
                grapes.erase(remove(grapes.begin(), grapes.end(), ui), grapes.end());
            } else {
                hasGrape[ui] = true;
                grapes.push_back(ui);
            }
        } else if (query.type == 3) {
            int ai = query.x, bi = query.y, wi = query.z;
            updateEdge(ai, bi, wi);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;

    adj.resize(n + 1);
    hasGrape.assign(n + 1, false);

    for (int i = 0; i < n - 1; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w, i});
        adj[b].push_back({a, w, i});
    }

    vector<Query> queries;

    for (int i = 0; i < q; i++) {
        int type, x, y = 0, z = 0;
        cin >> type >> x;
        if (type == 2) {
            queries.push_back({type, x, 0, 0});
        } else if (type == 3) {
            cin >> y >> z;
            queries.push_back({type, x, y, z});
        } else if (type == 1) {
            queries.push_back({type, x, 0, 0});
        }
    }

    processQueries(queries);

    return 0;
}

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