Submission #1111305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111305		namprozz	Grapevine (NOI22_grapevine)	C++17	6 / 100	67 ms	24032 KiB

Main

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

struct query
{
    ll t, a, b, c;
};

ll n, q;
vector<map<ll, ll>> adj;
vector<query> queries;

namespace sub1
{
    struct run
    {
        ll u;
        ll par;
        ll res;

        bool operator>(const run& other) const
        {
            return res > other.res;
        }
    };

    vector<bool> state;

    void solve()
    {
        state.resize(n, false);

        for(query &q : queries)
        {
            if(q.t == 1)
            {
                priority_queue<run, vector<run>, greater<run>> pq;
                pq.push({q.a - 1, -1, 0});
                ll res = -1;
                while(!pq.empty())
                {
                    run cur = pq.top();
                    ll u = cur.u;
                    pq.pop();

                    if(state[u])
                    {
                        res = cur.res;
                        break;
                    }

                    for(auto &i : adj[u])
                    {
                        ll v = i.first;
                        ll w = i.second;

                        if(v == cur.par)
                            continue;
                        pq.push({v, u, cur.res + w});
                    }
                }
                cout << res << '\n';
            }
            else if(q.t == 2)
            {
                ll u = q.a - 1;
                if(state[u])
                {
                    state[u] = false;
                }
                else
                {
                    state[u] = true;
                }
            }
            else
            {
                ll u = q.a - 1, v = q.b - 1, w = q.c;
                adj[u][v] = w;
                adj[v][u] = w;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;
    adj.resize(n);
    for(ll i = 0; i < n - 1; i++)
    {
        ll a, b, w;
        cin >> a >> b >> w;
        a--;
        b--;
        adj[a][b] = w;
        adj[b][a] = w;
    }
    queries.resize(q);
    for(auto &q : queries)
    {
        cin >> q.t;
        if(q.t == 1)
        {
            cin >> q.a;
        }
        else if(q.t == 2)
        {
            cin >> q.a;
        }
        else
        {
            cin >> q.a >> q.b >> q.c;
        }
    }

    if(n <= 2000 and q <= 2000)
    {
        sub1::solve();
    }
}

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