oj.uz

Submission #1111305

# Submission time Handle Problem Language Result Execution time Memory
1111305 2024-11-12T03:08:04 Z namprozz Grapevine (NOI22_grapevine) C++17
6 / 100
 67 ms 24032 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 848 KB Output is correct
2 Correct 4 ms 848 KB Output is correct
3 Correct 3 ms 932 KB Output is correct
4 Correct 8 ms 848 KB Output is correct
5 Correct 3 ms 848 KB Output is correct
6 Correct 3 ms 848 KB Output is correct
7 Correct 45 ms 1000 KB Output is correct
8 Correct 37 ms 996 KB Output is correct
9 Correct 37 ms 1004 KB Output is correct
10 Correct 8 ms 848 KB Output is correct
11 Correct 3 ms 848 KB Output is correct
12 Correct 3 ms 848 KB Output is correct
13 Correct 47 ms 1004 KB Output is correct
14 Correct 37 ms 848 KB Output is correct
15 Correct 34 ms 1008 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 23880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 24032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 23872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 23740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 848 KB Output is correct
2 Correct 4 ms 848 KB Output is correct
3 Correct 3 ms 932 KB Output is correct
4 Correct 8 ms 848 KB Output is correct
5 Correct 3 ms 848 KB Output is correct
6 Correct 3 ms 848 KB Output is correct
7 Correct 45 ms 1000 KB Output is correct
8 Correct 37 ms 996 KB Output is correct
9 Correct 37 ms 1004 KB Output is correct
10 Correct 8 ms 848 KB Output is correct
11 Correct 3 ms 848 KB Output is correct
12 Correct 3 ms 848 KB Output is correct
13 Correct 47 ms 1004 KB Output is correct
14 Correct 37 ms 848 KB Output is correct
15 Correct 34 ms 1008 KB Output is correct
16 Incorrect 67 ms 23880 KB Output isn't correct
17 Halted 0 ms 0 KB -