제출 #1151159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151159		12345678	Grapevine (NOI22_grapevine)	C++20	100 / 100	1422 ms	154168 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5, kx=17;

struct node
{
    ll mn, lz;
    node(): mn(0), lz(0){}
};

ll n, q, u, v, w, in[nx][kx], out[nx][kx], pa[nx], sz[nx], lvl[nx], used[nx], dif, t, open[nx], cur, segsz[nx], cnt, res;
vector<ll> d[nx];
vector<node> seg[nx];
map<pair<ll, ll>, ll> mp;
vector<tuple<ll, ll, ll>> edg;

int dfssz(int u, int p)
{
    sz[u]=1;
    for (auto v:d[u]) if (v!=p&&!used[v]) sz[u]+=dfssz(v, u);
    return sz[u];
}

int findcentroid(int u, int p, int rtsz)
{
    for (auto v:d[u]) if (v!=p&&!used[v]&&2*sz[v]>rtsz) return findcentroid(v, u, rtsz);
    return u;
}

void dfseulor(int u, int p, int hdlvl)
{
    in[u][hdlvl]=++t;
    for (auto v:d[u]) if (v!=p&&!used[v]) dfseulor(v, u, hdlvl);
    out[u][hdlvl]=t;
}

void decomposition(int u, int p)
{
    u=findcentroid(u, u, dfssz(u, u));
    used[u]=1;
    if (p!=-1) lvl[u]=lvl[p]+1;
    pa[u]=p;
    t=0;
    dfseulor(u, u, lvl[u]);
    segsz[u]=t;
    seg[u].resize(4*segsz[u]+5);
    for (auto v:d[u]) if (!used[v]) decomposition(v, u);
}

void pushlz(int idx, int l, int r, int i)
{
    seg[idx][i].mn+=seg[idx][i].lz;
    if (l!=r) seg[idx][2*i].lz+=seg[idx][i].lz, seg[idx][2*i+1].lz+=seg[idx][i].lz;
    seg[idx][i].lz=0;
}

void updateseg(int idx, int l, int r, int i, int ql, int qr, ll vl)
{
    pushlz(idx, l, r, i);
    if (qr<l||r<ql) return;
    if (ql<=l&&r<=qr) return seg[idx][i].lz=vl, pushlz(idx, l, r, i), void();
    int md=(l+r)/2;
    updateseg(idx, l, md, 2*i, ql, qr ,vl);
    updateseg(idx, md+1, r ,2*i+1, ql, qr ,vl);
    seg[idx][i].mn=min(seg[idx][2*i].mn, seg[idx][2*i+1].mn);
}

ll queryseg(int idx, int l, int r, int i, int ql, int qr)
{
    pushlz(idx, l, r, i);
    if (qr<l||r<ql) return 2e18;
    //if (ql==qr) cout<<"here "<<idx<<' '<<l<<' '<<r<<' '<<ql<<' '<<seg[idx][i].mn<<'\n';
    if (ql<=l&&r<=qr) return seg[idx][i].mn;
    int md=(l+r)/2;
    //ll vll=queryseg(idx, l, md, 2*i ,ql , qr), vlr=queryseg(idx, md+1, r, 2*i+1, ql, qr);
    //if (ql==qr) cout<<"return "<<idx<<' '<<l<<' '<<r<<' '<<ql<<' '<< vll<<' '<<vlr<<'\n';
    return min(queryseg(idx, l, md, 2*i ,ql , qr), queryseg(idx, md+1, r, 2*i+1, ql, qr));
}

void showseg(int idx, int l, int r, int i)
{
    pushlz(idx, l, r, i);
    if (l==r) return cout<<"show "<<idx<<' '<<l<<' '<<seg[idx][i].mn<<'\n', void();
    int md=(l+r)/2;
    showseg(idx, l, md, 2*i);
    showseg(idx, md+1, r, 2*i+1);
}

void updateedge(int u, int v, int w)
{
    if (u>v) swap(u, v);
    dif=w-mp[{u, v}];
    mp[{u, v}]=w;
    if (lvl[u]<lvl[v]) cur=u;
    else cur=v;
    while (cur!=-1)
    {
        if (in[u][lvl[cur]]<=in[v][lvl[cur]]&&out[v][lvl[cur]]<=out[u][lvl[cur]]) updateseg(cur, 1, segsz[cur], 1, in[v][lvl[cur]], out[v][lvl[cur]], dif);
        else updateseg(cur, 1, segsz[cur], 1, in[u][lvl[cur]], out[u][lvl[cur]], dif);
        cur=pa[cur];
    }
}

void updatenode(int u)
{
    if (open[u]) open[u]=0, dif=1e18, cnt--;
    else open[u]=1, dif=-1e18, cnt++;
    cur=u;
    while (cur!=-1)
    {
        updateseg(cur, 1, segsz[cur], 1, in[u][lvl[cur]], in[u][lvl[cur]], dif);
        cur=pa[cur];
    }
}

ll query(int u)
{
    if (cnt==0) return -1;
    cur=u;
    res=1e18;
    while (cur!=-1)
    {
        ll dist=queryseg(cur, 1, segsz[cur], 1, in[u][lvl[cur]], in[u][lvl[cur]]);
        if (dist>=1e18) dist-=(ll)1e18;
        //cout<<"in "<<in[u][lvl[cur]]<<'\n';
        //cout<<"dist "<<cur<<' '<<u<<' '<<dist<<'\n';
        //showseg(cur, 1, segsz[cur], 1);
        res=min(res, dist+queryseg(cur, 1, segsz[cur], 1, 1, segsz[cur]));
        cur=pa[cur];
    }
    return res;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q;
    cnt=n;
    for (int i=1; i<n; i++) cin>>u>>v>>w, d[u].push_back(v), d[v].push_back(u), mp[{min(u, v), max(u, v)}]=0, edg.push_back({u, v, w});
    decomposition(1, -1);
    for (int i=1; i<=n; i++) open[i]=1, updatenode(i);
    for (auto [u, v, w]:edg) updateedge(u, v, w);
    //showseg(3, 1, segsz[3], 1);
    while (q--)
    {
        cin>>t;
        if (t==1) cin>>u, cout<<query(u)<<'\n';
        if (t==2) cin>>u, updatenode(u);
        if (t==3) cin>>u>>v>>w, updateedge(u, v, w);
    }
}

/*
7 4
1 2 2
2 3 4
5 6 1
5 3 6
3 7 6
2 4 9
2 6
2 4
2 7
1 1
*/

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