Submission #1119441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119441		ro9669	Grapevine (NOI22_grapevine)	C++17	100 / 100	1846 ms	126716 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin() , v.end()
#define sz(v) int(v.size())
#define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
using namespace std;

typedef long long ll;
typedef pair<int , int> ii;
typedef pair<long long , int> lli;

const int maxN = int(1e5)+7;
const int LOG = 17;

int n , q;
map<ii , int> c;
vector<int> g[maxN];
bool del[maxN];
int sz[maxN];

void dfs_size(int u , int par){
    sz[u] = 1;
    for (int v : g[u]){
        if (del[v] == 0 && v != par){
            dfs_size(v , u);
            sz[u] += sz[v];
        }
    }
}

int dfs_find(int u , int par , int half){
    for (int v : g[u]){
        if (del[v] == 0 && v != par && sz[v] > half){
            return dfs_find(v , u , half);
        }
    }
    return u;
}

int p[maxN] , h[maxN] , in[LOG + 1][maxN] , out[LOG + 1][maxN] , DfsTime = 0;

void dfs_build(int u , int par , int d){
    in[d][u] = ++DfsTime;
    for (int v : g[u]){
        if (del[v] == 0 && v != par){
            dfs_build(v , u , d);
        }
    }
    out[d][u] = DfsTime;
}

void dfs_centroid(int u , int par){
    dfs_size(u , 0);
    u = dfs_find(u , 0 , sz[u] / 2);
    del[u] = 1;
    p[u] = par;
    h[u] = (par != 0) ? h[par] + 1 : 0;
    dfs_build(u , 0 , h[u]);
    for (int v : g[u]){
        if (del[v] == 0){
            dfs_centroid(v , u);
        }
    }
}

const ll inf = ll(1e17);

struct node{
    ll val , lazy;
};

node st[4 * LOG * maxN];

void init(){
    for (int id = 1 ; id <= 4 * DfsTime ; id++){
        st[id].val = inf;
        st[id].lazy = 0;
    }
}

void modify(int id , ll x){
    st[id].val += x;
    st[id].lazy += x;
}

#define lef(id) id * 2
#define rig(id) id * 2 + 1

void down(int id){
    ll &x = st[id].lazy;
    if (x == 0) return;
    modify(lef(id) , x);
    modify(rig(id) , x);
    x = 0;
}

void update(int id , int l , int r , int u , int v , ll x){
    if (v < l || r < u) return;
    if (u <= l && r <= v) return modify(id , x);
    if (l != r) down(id);
    int mid = (l + r) / 2;
    update(lef(id) , l , mid , u , v , x);
    update(rig(id) , mid + 1 , r , u , v , x);
    st[id].val = min(st[lef(id)].val , st[rig(id)].val);
}

ll get(int id , int l , int r , int u , int v){
    if (v < l || r < u) return 2 * inf;
    if (u <= l && r <= v) return st[id].val;
    if (l != r) down(id);
    int mid = (l + r) / 2;
    return min(get(lef(id) , l , mid , u , v) , get(rig(id) , mid + 1 , r , u , v));
}

void update(int u , int v , ll w){
    int x = (h[u] < h[v]) ? u : v;
    for (; x != 0 ; x = p[x]){
        if (in[h[x]][u] > in[h[x]][v]) swap(u , v);
        update(1 , 1 , DfsTime , in[h[x]][v] , out[h[x]][v] , +w);
    }
}

bool type[maxN];

void update(int u){
    if (type[u] == 0){
        type[u] = 1;
        for (int x = u ; x != 0 ; x = p[x]){
            update(1 , 1 , DfsTime , in[h[x]][u] , in[h[x]][u] , -inf);
        }
    }
    else{
        type[u] = 0;
        for (int x = u ; x != 0 ; x = p[x]){
            update(1 , 1 , DfsTime , in[h[x]][u] , in[h[x]][u] , +inf);
        }
    }
}

ll get(int u){
    ll ans = inf;
    for (int x = u ; x != 0 ; x = p[x]){
        ll a = get(1 , 1 , DfsTime , in[h[x]][u] , in[h[x]][u]);
        if (type[u] == 0) a -= inf;
        ll b = get(1 , 1 , DfsTime , in[h[x]][x] , out[h[x]][x]);
        ans = min(ans , a + b);
    }
    if (ans == inf) ans = -1;
    return ans;
}

void solve(){
    cin >> n >> q;
    for (int i = 1 ; i < n ; i++){
        int u , v , w;
        cin >> u >> v >> w;
        g[u].push_back(v);
        g[v].push_back(u);
        c[{min(u , v) , max(u , v)}] = w;
    }
    dfs_centroid(1 , 0);
    init();
    for (auto it : c){
        int u = it.fi.fi;
        int v = it.fi.se;
        int w = it.se;
        update(u , v , w);
    }
    while (q--){
        int t; cin >> t;
        if (t == 1){
            int u; cin >> u;
            cout << get(u) << "\n";
        }
        if (t == 2){
            int u; cin >> u;
            update(u);
        }
        if (t == 3){
            int u , v , w;
            cin >> u >> v >> w;
            ii it = {min(u , v) , max(u , v)};
            update(u , v , w - c[it]);
            c[it] = w;
        }
    }
}

#define name "A"

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(name".INP" , "r")){
        freopen(name".INP" , "r" , stdin);
        freopen(name".OUT" , "w" , stdout);
    }
    int t = 1; //cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:195:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  195 |         freopen(name".INP" , "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:196:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  196 |         freopen(name".OUT" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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