Submission #1124397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124397		TVSown	Grapevine (NOI22_grapevine)	C++20	100 / 100	1362 ms	219276 KiB

Main

///*** Sown_Vipro ***///
/// ->TUYEN QUOC GIA<- ///

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("popcnt")
#define F first
#define S second
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define all(a) a.begin(), a.end()
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
#define out(name) if(fopen(name, "w")) freopen(name, "w", stdout);
#define szz(s) int(s.size())
//#define int long long
const int N = 1e5 + 5, MAX = 1e6, MOD = 1e9 + 7;
const long long oo = 1e18;
int n, q, TIME, tidel;
int cnt[N], sz[N], del[N], nxt[N], h[N];
vector<pi> e[N];
vector<int> c[N];
vector<long long> m[N], lz[N], s[N];
pi ti[105][N];
map<int, int> W[N];

void down(int cen, int id){
    if(lz[cen][id]){
        s[cen][2 * id] += lz[cen][id];
        if(m[cen][2 * id] < oo) m[cen][2 * id] += lz[cen][id];
        lz[cen][2 * id] += lz[cen][id];

        s[cen][2 * id + 1] += lz[cen][id];
        if(m[cen][2 * id + 1] < oo) m[cen][2 * id + 1] += lz[cen][id];
        lz[cen][2 * id + 1] += lz[cen][id];

        lz[cen][id] = 0;
    }
}

void update(int cen, int id, int l, int r, int u, int v, long long x){
    if(l > v || r < u) return;
    if(u <= l && r <= v){
        s[cen][id] += x;
        if(m[cen][id] < oo) m[cen][id] += x;
        lz[cen][id] += x;
        return;
    }
    down(cen, id);
    int mid = (l + r) / 2;
    update(cen, 2 * id, l, mid, u, v, x);
    update(cen, 2 * id + 1, mid + 1, r, u, v, x);

    m[cen][id] = min(m[cen][2 * id], m[cen][2 * id + 1]);
}

void update2(int cen, int id, int l, int r, int i){
    if(i > r || i < l) return;
    if(l == r){
        c[cen][id] ^= 1;
        m[cen][id] = (c[cen][id] ? s[cen][id] : oo);
//        cout << s[cen][id] << "\n";
        return;
    }
    down(cen, id);
    int mid = (l + r) / 2;
    update2(cen, 2 * id, l, mid, i);
    update2(cen, 2 * id + 1, mid + 1, r, i);

    m[cen][id] = min(m[cen][2 * id], m[cen][2 * id + 1]);
}

long long dis(int cen, int id, int l, int r, int u, int v){
    if(l > v || r < u) return 0;
    if(u <= l && r <= v){
        return s[cen][id];
    }
    down(cen, id);
    int mid = (l + r) / 2;
    return dis(cen, 2 * id, l, mid, u, v) + dis(cen, 2 * id + 1, mid + 1, r, u, v);
}


void count_child(int u, int p){
    cnt[u] = 1;
    for(auto [v, w] : e[u]){
        if(v != p && !del[v]){
            count_child(v, u);
            cnt[u] += cnt[v];
        }
    }
}

int find_centroid(int u, int p, int n){
    for(auto [v, w] : e[u]){
        if(v != p && !del[v] && cnt[v] > (n / 2)) return find_centroid(v, u, n);
    }
    return u;
}

void dfs(int u, int p, long long W, int cen){
    ti[h[cen]][u].F = ++TIME;
    update(cen, 1, 1, sz[cen], TIME, TIME, W);

    for(auto [v, w] : e[u]){
        if(v != p && !del[v]){
            dfs(v, u, W + w, cen);
        }
    }
    ti[h[cen]][u].S = TIME;
//    ti[cen][u] = {in[u], out[u]};
}

void build(int u, int p){
    count_child(u, p);
    int cen = find_centroid(u, p, cnt[u]);
    h[cen] = (p ? h[p] + 1 : 0);
    nxt[cen] = p;
    sz[cen] = cnt[u];
//    cout << cen << " " << cnt[u] << "\n";
    s[cen] = vector<long long> (4 * cnt[u], 0);
    c[cen] = vector<int> (4 * cnt[u], 0);
    m[cen] = vector<long long> (4 * cnt[u], oo);
    lz[cen] = vector<long long> (4 * cnt[u], 0);

    TIME = 0;
    dfs(cen, p, 0, cen);
//    cout << ti[cen][3].F << " " << dis(cen, 1, 1, sz[cen], ti[cen][3].F, ti[cen][3].F) << "\n";
    del[cen] = ++tidel;

    for(auto [v, w] : e[cen]){
        if(!del[v]) build(v, cen);
    }
}

void solve(){
    cin >> n >> q;
    FOR(i, 2, n){
        int u, v, w; cin >> u >> v >> w;
        if(u > v) swap(u, v);
        e[u].pb({v, w});
        e[v].pb({u, w});
        W[u][v] = W[v][u] = w;
    }
    build(1, 0);

    while(q--){
        int t; cin >> t;
        if(t == 1){
            int s; cin >> s;
            long long res = oo, u = s;
            while(u != 0){
                long long cost = dis(u, 1, 1, sz[u], ti[h[u]][s].F, ti[h[u]][s].F) + m[u][1];
                res = min(res, cost);
                u = nxt[u];
            }
            cout << (res > 1e14 ? -1 : res) << "\n";
        }else if(t == 2){
            int s; cin >> s;
            int u = s;
            while(u != 0){
                update2(u, 1, 1, sz[u], ti[h[u]][s].F);
                u = nxt[u];
            }
        }else{
            int s, t, w; cin >> s >> t >> w;
            if(del[s] > del[t]) swap(s, t);
            int u = s;
            while(u != 0){
                if(ti[h[u]][s].F > ti[h[u]][t].F) swap(s, t);
                update(u, 1, 1, sz[u], ti[h[u]][t].F, ti[h[u]][t].S, w - W[s][t]);
//                cout << u << " " << s << " " << t << " " << w << " " << w - W[{s, t}] << " " << m[u][1] << "\n";
                u = nxt[u];
            }
            if(s > t) swap(s, t);
            W[s][t] = W[t][s] = w;
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    inp("sown.inp");
//    out("out.txt");
    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:17:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 | #define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:188:5: note: in expansion of macro 'inp'
  188 |     inp("sown.inp");
      |     ^~~

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