Submission #960019

#	Time	Username	Problem	Language	Result	Execution time	Memory
960019		Cookie	Grapevine (NOI22_grapevine)	C++14	100 / 100	2221 ms	243056 KiB

Main

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
//const int x[4] = {1, 0, -1, 0};
//const int y[4] = {0, -1, 0, 1};
const ll mod = 1e9 + 69, pr = 31;
const int mxn = 1e5 + 5, mxq = 1e5 + 5, sq = 300, mxv = 5e4 + 1;
//const int base = (1 <<18);
const ll inf = 1e18 + 5, neg = -69420, inf2 = 1e16;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// have fun!
// <3;
struct ST{
    vt<ll>st, lz;
    void init(int siz, bool bad){
        st.resize(4 * siz + 1, 0); lz.resize(4 * siz + 1, 0);
        if(bad){
            for(int i = 1; i <= 4 * siz; i++)st[i] = inf;
        }
    }
    void push(int nd){
        ll &v = lz[nd];
        lz[nd << 1] += v; lz[nd << 1 | 1] += v; st[nd << 1] += v; st[nd << 1 | 1] += v;
        v = 0;
    }
    void change(int nd, int l, int r, int id, ll v){
        if(id > r || id < l)return;
        if(l == r){
            st[nd] = v;
            return;
        }
        int mid = (l + r) >> 1;
        push(nd);
        change(nd << 1, l, mid, id, v); change(nd << 1 | 1, mid + 1, r, id, v);
        st[nd] = min(st[nd << 1], st[nd << 1 | 1]);
    }
    void upd(int nd, int l, int r, int ql, int qr, ll v){
        if(ql > r || qr < l)return;
        if(ql <= l && qr >= r){
            st[nd] += v; lz[nd] += v;
            return;
        }   
        push(nd);
        int mid = (l + r) >> 1;
        upd(nd << 1, l, mid, ql, qr, v); upd(nd << 1 | 1, mid + 1, r, ql, qr, v);
        st[nd] = min(st[nd << 1], st[nd << 1 | 1]);
    }
    ll get(int nd, int l, int r, int id){
        if(id > r || id < l)return(inf);
        if(l == r)return(st[nd]);
        push(nd);
        int mid = (l + r) >> 1;
        return(min(get(nd << 1, l, mid, id), get(nd << 1 | 1, mid + 1, r, id)));
    }
};

ST st[mxn + 1], st2[mxn + 1];
int n, q;
vt<pii>adj[mxn + 1];
int tin[20][mxn + 1], tout[20][mxn + 1], tt[mxn + 1], siz[mxn + 1], dep[mxn + 1], pa[mxn + 1];
bool vis[mxn + 1], on[mxn + 1];
int dfs(int s, int pre){
    siz[s] = 1;
    for(auto [i, w]: adj[s]){
        if(i != pre && !vis[i]){
            siz[s] += dfs(i, s);
        }
    }
    return(siz[s]);
}
int centroid(int s, int pre, int need){
    for(auto [i, w]: adj[s]){
        if(i != pre && !vis[i] && siz[i] * 2 > need)return(centroid(i, s, need));
    }
    return(s);
}
void dfs2(int s, int pre, int depth,int root){
    tin[depth][s] = ++tt[root];
    for(auto [v, w]: adj[s]){
        if(!vis[v] && v != pre){
            dfs2(v, s, depth, root);
        }
    }
    tout[depth][s] = tt[root];
}
ll eu[mxn + 1], ev[mxn + 1], ew[mxn + 1];
void build(int s, int pre, int depth){
    int c = centroid(s, -1, dfs(s, -1)); dep[c] = depth; pa[c] = pre;
   
    vis[c] = 1; 
    st[c].init(siz[s], 0); st2[c].init(siz[s], 1);
    dfs2(c, -1 , depth,c);
    for(auto [i, w]: adj[c]){
        if(!vis[i]){
            build(i, c, depth + 1);
        }
    }
}
map<pii, int>toe;
void anneal(int u, int v, ll w){
    if(dep[u] > dep[v])swap(u, v);
    int node = u;

    for(int i = dep[u]; i >= 0; i--){
        int at = ((tin[i][u] < tin[i][v]) ? v : u);
        st[node].upd(1, 1, tt[node], tin[i][at], tout[i][at], w);
        st2[node].upd(1, 1, tt[node], tin[i][at], tout[i][at], w);
        //if(i == 0)cout << tin[i][v] << ' ' << tout[i][v] << " " << w << "\n";
        node = pa[node];
    }
}
void seek(int u){
    ll ans = inf;
    int node = u;
    for(int i = dep[u]; i >= 0; i--){
        //cout << node << " " << st2[node].st[1] << "\n";
        ans = min(ans, st[node].get(1, 1, tt[node], tin[i][u]) + st2[node].st[1]);
        node = pa[node];
    }
    cout << ((ans >= inf2) ? -1 : ans) << "\n";
}
void soak(int u){
    int node = u;
    for(int i = dep[u]; i >= 0; i--){
        if(on[u])st2[node].change(1, 1, tt[node], tin[i][u], st[node].get(1, 1, tt[node], tin[i][u]));
        else st2[node].change(1, 1, tt[node], tin[i][u], inf);
        node = pa[node];
    }
}
void solve(){
    cin >> n >> q;
    for(int i = 1; i < n; i++){
        cin >> eu[i] >> ev[i] >> ew[i];
        if(eu[i] > ev[i])swap(eu[i], ev[i]); toe[mpp(eu[i], ev[i])] = i;
        adj[eu[i]].pb(mpp(ev[i], ew[i]));  adj[ev[i]].pb(mpp(eu[i], ew[i]));
    }
    
    build(1, -1, 0);
    for(int i = 1; i < n; i++){
        anneal(eu[i], ev[i], ew[i]);
    }
    
    while(q--){
        int idq; cin >> idq;
        if(idq == 1){
            int u; cin >> u; seek(u);
        }else if(idq == 2){
            
            int u; cin >> u; on[u] = !on[u]; soak(u);
        }else{
            int a, b, w; cin >> a >> b >> w; if(a > b)swap(a, b); 
            ll crw = ew[toe[mpp(a, b)]]; 
            anneal(a, b, w - crw); ew[toe[mpp(a, b)]] = w;
        }
    }
}


signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("netw.inp", "r", stdin);
    //freopen("netw.out", "w", stdout);
    int ttt; ttt = 1;
    while(ttt--){
        solve();

    }
    return(0);
}
/*
1
5 7 2
1 1 1
3 1 2
2 2 3
4 2 4
2 4 2
1 5 5
3 5 2
5 3
2 7
3 3 1
1 1 1
1 2 2
1 3 3
3 1
*/

Compilation message (stderr)

Main.cpp: In function 'int dfs(int, int)':
Main.cpp:81:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |     for(auto [i, w]: adj[s]){
      |              ^
Main.cpp: In function 'int centroid(int, int, int)':
Main.cpp:89:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |     for(auto [i, w]: adj[s]){
      |              ^
Main.cpp: In function 'void dfs2(int, int, int, int)':
Main.cpp:96:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |     for(auto [v, w]: adj[s]){
      |              ^
Main.cpp: In function 'void build(int, int, int)':
Main.cpp:110:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  110 |     for(auto [i, w]: adj[c]){
      |              ^
Main.cpp: In function 'void solve()':
Main.cpp:151:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  151 |         if(eu[i] > ev[i])swap(eu[i], ev[i]); toe[mpp(eu[i], ev[i])] = i;
      |         ^~
Main.cpp:151:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  151 |         if(eu[i] > ev[i])swap(eu[i], ev[i]); toe[mpp(eu[i], ev[i])] = i;
      |                                              ^~~

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