Submission #767073

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
767073	2023-06-26T11:08:20 Z	birthdaycake	Grapevine (NOI22_grapevine)	C++17	15 / 100	574 ms	29456 KB

Main

#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
 
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
 
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
 
 
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#define endl '\n'
#define int long long
#define mod 1000000007
using namespace std;

vector<int>adj[200001];
int g[200001],sub[200001];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,q; cin >> n >> q;
    map<pair<int,int>,int>d;
    for(int i = 0; i < n - 1; i++){
        int a,b,c; cin >> a >> b >> c;
        d[{a,b}] = c;
        d[{b,a}] = c;
    }
    for(int i = 1; i <= 2 * n + 1; i++) sub[i] = 1e18;
    while(q--){
        int t; cin >> t;
        if(t == 1){
            int node; cin >> node;
            int ans = 1e18, dist = 0;
            while(node > 0){
                if(sub[node] != 1e18) ans = min(ans, sub[node] + dist);
                dist += d[{node / 2, node}];
                node /= 2;
            }
            if(ans == 1e18) ans = -1;
            cout << ans << endl;
        }else if(t == 2){
            int grape; cin >> grape;
            g[grape] = !g[grape];
            if(g[grape]){
                while(grape > 0){
                    sub[grape] = min(sub[grape * 2] + d[{grape * 2, grape}], sub[grape * 2 + 1] + d[{grape * 2 + 1, grape}]);
                    if(g[grape]) sub[grape] = 0;
                    grape /= 2;
                }
            }else{
                sub[grape] = 1e18;
                while(grape > 0){
                    sub[grape] = min(sub[grape * 2] + d[{grape * 2, grape}], sub[grape * 2 + 1] + d[{grape * 2 + 1, grape}]);
                    if(g[grape]) sub[grape] = 0;
                    grape /= 2;
                }
            }
            
        }else{
            int a,b,c; cin >> a >> b >> c;
            d[{a,b}] = c;
            d[{b,a}] = c;
            a = min(a,b);
            while(a > 0){
                sub[a] = min(sub[a * 2] + d[{a * 2, a}], sub[a * 2 + 1] + d[{a * 2 + 1, a}]);
                if(g[a]) sub[a] = 0;
                a /= 2;
            }
        }
    }
    
    return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 14.0

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

Subtask #3
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	439 ms	21028 KB	Output is correct
2	Correct	447 ms	21096 KB	Output is correct
3	Correct	443 ms	21400 KB	Output is correct
4	Correct	469 ms	20892 KB	Output is correct
5	Correct	442 ms	22964 KB	Output is correct
6	Correct	438 ms	23380 KB	Output is correct
7	Correct	458 ms	22368 KB	Output is correct
8	Correct	478 ms	22948 KB	Output is correct
9	Correct	451 ms	23352 KB	Output is correct
10	Correct	492 ms	23444 KB	Output is correct
11	Correct	522 ms	23576 KB	Output is correct
12	Correct	475 ms	23204 KB	Output is correct
13	Correct	504 ms	22104 KB	Output is correct
14	Correct	522 ms	21940 KB	Output is correct
15	Correct	507 ms	22728 KB	Output is correct