oj.uz

Submission #766278

# Submission time Handle Problem Language Result Execution time Memory
766278 2023-06-25T12:39:47 Z birthdaycake Grapevine (NOI22_grapevine) C++17
14 / 100
 300 ms 29268 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];
int cnt = 1,N,Left,Right,Val,T;
void dfs(int x){
    l[x] = cnt++;
    for(auto s: adj[x]){
        if(s.first != p[x]){
            p[s.first] = x;
            v[s.first] = v[x] + s.second;
            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;
}
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;
    for(int i = 0; i < q; i++){
        int t; cin >> t;
        if(t == 1){
            int s; cin >> s;
            if(seg[1][1]){
                cout << seg[1][0] << endl;
            }else{
                cout << -1 << endl;
            }
        }else if(t == 2){
            int vv; cin >> vv;
            grape[vv] = !grape[vv];
            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.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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 26032 KB Output is correct
2 Correct 272 ms 25604 KB Output is correct
3 Correct 252 ms 25760 KB Output is correct
4 Correct 233 ms 27324 KB Output is correct
5 Correct 223 ms 26100 KB Output is correct
6 Correct 236 ms 26396 KB Output is correct
7 Correct 203 ms 25244 KB Output is correct
8 Correct 245 ms 26300 KB Output is correct
9 Correct 218 ms 26644 KB Output is correct
10 Correct 272 ms 28748 KB Output is correct
11 Correct 267 ms 29268 KB Output is correct
12 Correct 285 ms 27524 KB Output is correct
13 Correct 234 ms 26852 KB Output is correct
14 Correct 238 ms 26568 KB Output is correct
15 Correct 203 ms 26864 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 18.0

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

Subtask #6
0 / 32.0

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