oj.uz

Submission #1111306

# Submission time Handle Problem Language Result Execution time Memory
1111306 2024-11-12T03:09:25 Z namprozz Grapevine (NOI22_grapevine) C++17
6 / 100
 3000 ms 21300 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 11 ms 848 KB Output is correct
2 Correct 6 ms 860 KB Output is correct
3 Correct 2 ms 848 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 42 ms 944 KB Output is correct
8 Correct 37 ms 944 KB Output is correct
9 Correct 33 ms 848 KB Output is correct
10 Correct 10 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 848 KB Output is correct
14 Correct 43 ms 848 KB Output is correct
15 Correct 33 ms 848 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3060 ms 20808 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3042 ms 21300 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3050 ms 20628 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3050 ms 20724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 848 KB Output is correct
2 Correct 6 ms 860 KB Output is correct
3 Correct 2 ms 848 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 42 ms 944 KB Output is correct
8 Correct 37 ms 944 KB Output is correct
9 Correct 33 ms 848 KB Output is correct
10 Correct 10 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 848 KB Output is correct
14 Correct 43 ms 848 KB Output is correct
15 Correct 33 ms 848 KB Output is correct
16 Execution timed out 3060 ms 20808 KB Time limit exceeded
17 Halted 0 ms 0 KB -