Submission #766323

#	Time	Username	Problem	Language	Result	Execution time	Memory
766323		birthdaycake	Grapevine (NOI22_grapevine)	C++17	15 / 100	367 ms	54692 KiB

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<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 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 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});
        d[{min(a,b), max(a,b)}] = c;
    }
    dfs(1);
    N = exp2(ceil(log2(n)));
    for(int i = 1; i <= n; i++)  seg[l[i] + N - 1][0] = v[i];
    for(int i = N - 1; i > 0; i--) seg[i][0] = 1e18;
    
    int curr = 0;
    for(int i = 0; i < q; i++){
        int t; cin >> t;
        if(t == 1){
            int s; cin >> s;
            int nw = lca(s, curr), ans = 0;
            if(curr == 0){
                cout << -1 << endl;
                continue;
            }
            Left = l[s]; Right = l[s];
            ans += Query();
            Left = l[curr]; Right = l[curr];
            ans += Query();
            Left = l[nw]; Right = l[nw];
            ans -= (2 * Query());
            
            cout << ans << endl;
            
            
            
        }else if(t == 2){
            int vv; cin >> vv;
            grape[vv] = !grape[vv];
            if(grape[vv]) curr = vv;
            else curr = 0;
            T = grape[vv];
            Left = l[vv]; Right = l[vv];
            Update();
        }else{
            int a,b,c; cin >> a >> b >> c;
            Val = c - d[{min(a,b), max(a,b)}];
            if(p[a] == b) {Left = l[a]; Right = r[a];}
            else {Left = l[b]; Right = r[b];}
            T = -1;
            Update();
            d[{min(a,b), max(a,b)}] = c;
        }
    }
}
/*
 2 4
 1 1
 
 
 4
 
 3 1 3 2
 1 1
 
 2
 
 2 3
 3 2 1 2
 2 4
 1 1
 
 
 */

• Subtask 1: 0 / 6
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 15 / 15
• Subtask 5: 0 / 18
• Subtask 6: 0 / 32