Submission #766441

# Submission time Handle Problem Language Result Execution time Memory
766441 2023-06-25T16:16:05 Z birthdaycake Grapevine (NOI22_grapevine) C++14
0 / 100
578 ms 46788 KB
#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<pair<int,int>>adj[200001];
int grape[200001], p[200001],seg[1000001][2],v[200001],l[200001],r[200001],lazy[1000001], depth[200001];
int cnt = 1,N,Left,Right,Val,T;
int sub[200001];
int sparse[200001][30];
void dfs(int x){
    depth[x]++;
    sparse[x][0] = p[x];
    for(int j = 1; (1 << j) <= depth[x]; j++) sparse[x][j] = sparse[sparse[x][j - 1]][j - 1];
    l[x] = cnt++;
    for(auto s: adj[x]){
        if(s.first != p[x]){
            p[s.first] = x;
            v[s.first] = v[x] + s.second;
            depth[s.first] += depth[x];
            dfs(s.first);
        }
    }
    r[x] = cnt - 1;
}
void Spread(int ind){
    if(lazy[ind] != 0){
        seg[ind * 2][0] += lazy[ind];
        seg[ind * 2 + 1][0] += lazy[ind];
        lazy[ind * 2] += lazy[ind];
        lazy[ind * 2 + 1]+= lazy[ind];
    }
    lazy[ind] = 0;
}
 
void Update(int ll = 1, int rr = N, int ind = 1){
    if(ll > Right or rr < Left) return;
    if(ll != rr) Spread(ind);
    if(ll >= Left and rr <= Right){
        if(T == 0) seg[ind][1] = 0;
        else if(T == 1) seg[ind][1] = 1;
        else{
            seg[ind][0] += Val;
            lazy[ind] += Val;
        }
        return;
    }
    int mid = (ll + rr) / 2;
    Update(ll, mid, ind * 2);
    Update(mid + 1, rr, ind * 2 + 1);
    int v1 = 1e18, v2 = 1e18;
    if(seg[ind * 2][1]) v1 = seg[ind * 2][0];
    if(seg[ind * 2 + 1][1]) v2 = seg[ind * 2 + 1][0];
    seg[ind][0] = min(v1,v2);
    if(seg[ind][0] != 1e18) seg[ind][1] = 1;
    else seg[ind][1] = 0;
}
int Query(int ll = 1, int rr = N, int ind = 1){
    if(ll > Right or rr < Left) return 0;
    if(ll != rr) Spread(ind);
    if(ll >= Left and rr <= Right) return seg[ind][0];
    int mid = (ll + rr) / 2;
    return Query(ll, mid, ind * 2) + Query(mid + 1, rr, ind * 2 + 1);
}
int Query2(int ll = 1, int rr = N, int ind = 1){
    if(ll > Right or rr < Left) return 1e18;
    if(ll != rr) Spread(ind);
    if(ll >= Left and rr <= Right) {
        if(seg[ind][1]) return seg[ind][0];
        return 1e18;
    }
    int mid = (ll + rr) / 2;
    return min(Query2(ll, mid, ind * 2), Query2(mid + 1, rr, ind * 2 + 1));
}
 
 
int lca(int a, int b){
    if(depth[a] > depth[b]) swap(a,b);
    
    int diff = depth[b] - depth[a];
    for(int j = 0; j < 30; j++){
        if(diff & (1 << j)){
            b = sparse[b][j];
        }
    }
    for(int j = 29; j >= 0; j--){
        if(sparse[a][j] != sparse[b][j]){
            a = sparse[a][j];
            b = sparse[b][j];
        }
    }
    if(a != b) return sparse[a][0];
    return a;
}
signed main(){
    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;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    for(int i = 1; i <= n; i++) sub[i] = 1e18;
    dfs(1);
    for(int i = 0; i < q; i++){
        int t; cin >> t;
        if(t == 1){
            int s, ans = 1e18; cin >> s;
            int dist = 0, x = s;
            while(x != 1){
                int y = x;
                while(y != 1){
                    dist += d[{y/2,y}];
                    y/=2;
                }
                if(sub[x] != 1e18){
                    ans = min(ans, sub[x] + dist);
                }
                dist = 0;
                x /= 2;
            }
            cout << ans << endl;
            
            
        }else if(t == 2){
            int vv; cin >> vv;
            grape[vv] = !grape[vv];
            if(grape[vv]){
                sub[vv] = 0;
                while(vv > 0){
                    sub[vv/2] = min(sub[vv/2],sub[vv] + d[{vv/2,vv}]);
                    vv/=2;
                }
            }else{
                sub[vv] = 1e18;
                if(vv * 2 <= n) sub[vv] = min(sub[vv * 2] + d[{vv,vv * 2}], sub[vv]);
                if(vv * 2 + 1 <= n) sub[vv] = min(sub[vv * 2 + 1] + d[{vv, vv * 2 + 1}], sub[vv]);
                while(vv > 0){
                    sub[vv/2] = min(sub[vv/2],sub[vv] + d[{vv/2,vv}]);
                    vv/=2;
                }
            }
            
        }else{
            int a,b,c; cin >> a >> b >> c;
            Val = c - d[{min(a,b), max(a,b)}];
            d[{min(a,b), max(a,b)}] = c;
            int vv = min(a,b);
            while(vv > 0){
                sub[vv] = 1e8;
                if(vv * 2 <= n) sub[vv] = min(sub[vv * 2] + d[{vv,vv * 2}], sub[vv]);
                if(vv * 2 + 1 <= n) sub[vv] = min(sub[vv * 2 + 1] + d[{vv, vv * 2 + 1}], sub[vv]);
                vv/=2;
            }
        }
    }
}
/*
 2 4
 1 1
 
 
 4
 
 3 1 3 2
 1 1
 
 2
 
 2 3
 3 2 1 2
 2 4
 1 1
 
 
 */
# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5844 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 375 ms 46772 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 482 ms 44860 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 465 ms 46788 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 578 ms 46636 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5844 KB Output isn't correct
2 Halted 0 ms 0 KB -