oj.uz

Submission #758052

# Submission time Handle Problem Language Result Execution time Memory
758052 2023-06-14T05:57:15 Z ProtonDecay314 Grapevine (NOI22_grapevine) C++17
6 / 100
 3000 ms 19132 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<vector<vector<ll>>> wgraph;

class CompareVec {
    public:
        bool operator()(vector<ll> a, vector<ll> b) {
            return a[1] > b[1];
        }
};

ll seek(ll qi, ll n, const wgraph& adj, const vector<bool>& has_grape) {
    vector<bool> vis(n, false);
    priority_queue<vector<ll>, vector<vector<ll>>, CompareVec> pq;
    
    vector<ll> s;
    s.push_back(qi);
    s.push_back(0ll);
    pq.push(s);

    while(!pq.empty()) {
        vector<ll> cur = pq.top();
        pq.pop();
        ll curnode = cur[0];
        ll curdist = cur[1];
        
        if(vis[curnode]) continue;
        vis[curnode] = true;

        if(has_grape[curnode]) return curdist;

        for(const vector<ll>& edge : adj[curnode]) {
            vector<ll> new_entry;
            new_entry.push_back(edge[0]);
            new_entry.push_back(edge[1] + curdist);
            pq.push(new_entry);
        }
    }

    return -1;
}

int main() {
    ll n, q;
    cin >> n >> q;
    wgraph adj;
    vector<bool> has_grape(n, false);
    for(ll i = 0ll; i < n; i++) {
        vector<vector<ll>> row;
        adj.push_back(row);
    }

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

    while(q--) {
        ll qtype;
        cin >> qtype;

        if(qtype == 1) {
            // Seek
            ll qi;
            cin >> qi;
            qi--;
            cout << seek(qi, n, adj, has_grape) << endl;

        } else if(qtype == 2) {
            // Soak
            ll u;
            cin >> u;
            u--;
            has_grape[u] = !has_grape[u];
        } else {
            // Anneal
            ll qa, qb, qw;
            cin >> qa >> qb >> qw;
            qa--; qb--;

            for(vector<ll>& edge : adj[qa]) {
                if(edge[0] == qb) {
                    edge[1] = qw;
                }
            }

            for(vector<ll>& edge : adj[qb]) {
                if(edge[0] == qa) {
                    edge[1] = qw;
                }
            }
        }
    }

    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 596 KB Output is correct
2 Correct 38 ms 612 KB Output is correct
3 Correct 13 ms 596 KB Output is correct
4 Correct 129 ms 596 KB Output is correct
5 Correct 37 ms 468 KB Output is correct
6 Correct 27 ms 596 KB Output is correct
7 Correct 474 ms 716 KB Output is correct
8 Correct 346 ms 844 KB Output is correct
9 Correct 259 ms 764 KB Output is correct
10 Correct 139 ms 576 KB Output is correct
11 Correct 27 ms 640 KB Output is correct
12 Correct 26 ms 648 KB Output is correct
13 Correct 508 ms 772 KB Output is correct
14 Correct 320 ms 776 KB Output is correct
15 Correct 279 ms 728 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 15752 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 3060 ms 19132 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 3022 ms 15432 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 3027 ms 16048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 596 KB Output is correct
2 Correct 38 ms 612 KB Output is correct
3 Correct 13 ms 596 KB Output is correct
4 Correct 129 ms 596 KB Output is correct
5 Correct 37 ms 468 KB Output is correct
6 Correct 27 ms 596 KB Output is correct
7 Correct 474 ms 716 KB Output is correct
8 Correct 346 ms 844 KB Output is correct
9 Correct 259 ms 764 KB Output is correct
10 Correct 139 ms 576 KB Output is correct
11 Correct 27 ms 640 KB Output is correct
12 Correct 26 ms 648 KB Output is correct
13 Correct 508 ms 772 KB Output is correct
14 Correct 320 ms 776 KB Output is correct
15 Correct 279 ms 728 KB Output is correct
16 Execution timed out 3063 ms 15752 KB Time limit exceeded
17 Halted 0 ms 0 KB -