Submission #1125627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125627		goldencheems	Grapevine (NOI22_grapevine)	C++17	0 / 100	276 ms	146300 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pu push_back
#define ll long long
typedef pair <ll,ll> ii;
const int N=1e6;
long long mod=1e9;
int n,m,o[N+10];
ll w[N+1],pa[N+1],d[N+10],in[N+10],out[N+10],i_in[N+10],t;
vector <ii> adj[N+1];
//priority_queue <ll,vector<ll>,greater<ll>
map <int,int> dis[N+1],g[N+1];
bool vs[N+10];
struct truyvan{
    int id,u,v;
    ll w;
    };
truyvan tv[N+10];
ll calc(int u,int p){
    ll res=mod;
    if(o[u]) return 0;
    for(ii x:adj[u]){
        auto [v,i]=x;
        if(v==p) continue;
        res=min(res,calc(v,u)+w[i]);
    }
    return res;
    }
void dfs(int u,int p){
    t++;
    pa[u]=p;
    in[u]=t;
    i_in[t]=u;
    for(ii x:adj[u]){
        auto [v,i]=x;
        if(v==p) continue;
        d[v]=d[u]+w[i];
        dfs(v,u);
    }
    out[u]=t;
    }
void sub1(){
    while(m--){
        int x,u;
        cin>>x>>u;
        if(x==1){
            ll res=calc(u,0);
            if(res==mod) res=-1;
            cout<<res<<'\n';
        }
        else if(x==2){
            o[u]^=1;
        }
        else{
            ll v,W;
            cin>>v>>W;
            w[g[u][v]]=W;
        }
    }
    }
struct node{
    long lazy;
    long val;
    int i;
    };
node s[N*4+1];
node ss(int id,node a,node b){
    if(a.i<b.i) swap(a,b);
    if(a.i!=b.i) return a;
    node f=a;
    f.val=max(f.val,b.val);
    f.lazy=s[id].lazy;
    return f;
    }
void down(int id){
    ll t=s[id].lazy;
    if(t!=0){
    s[id*2].val+=t;
    s[id*2].lazy+=t;
    s[id*2+1].val+=t;
    s[id*2+1].lazy+=t;
    }
    s[id].lazy=0;
    }
void Build(int id,int l,int r){
    if(l==r){
        s[id].val=d[i_in[l]];
        s[id].i=0;
        return;
    }
    int mid=(l+r)/2;
    Build(id*2,l,mid);
    Build(id*2+1,mid+1,r);
    s[id]=ss(id,s[id*2],s[id*2+1]);
    }
void Update(int id,int l,int r,int u,int v,ll val){
    if(l>v || r<u) return;
    if(l>=u and r<=v){
        s[id].val+=val;
        s[id].lazy+=val;
        return;
    }
    down(id);
    int mid=(l+r)/2;
    Update(id*2,l,mid,u,v,val);
    Update(id*2+1,mid+1,r,u,v,val);
    s[id]=ss(id,s[id*2],s[id*2+1]);
    }
void Upd2(int id,int l,int r,int i){
    if(l>i || r<i) return;
    if(l==r){
        s[id].i^=1;
        return;
    }
    down(id);
    int mid=(l+r)/2;
    Upd2(id*2,l,mid,i);
    Upd2(id*2+1,mid+1,r,i);
    s[id]=ss(id,s[id*2],s[id*2+1]);
    }
node Find(int id,int l,int r,int u,int v){
    if(l>v || r<u) {
        node oo;
        oo.lazy=0;
        oo.val=mod;
        oo.i=0;
        return oo;
    }
    if(l>=u && r<=v) return s[id];
    int mid=(l+r)/2;
    down(id);
    node tg1=Find(id*2,l,mid,u,v);
    node tg2=Find(id*2+1,mid+1,r,u,v);
    return ss(id,tg1,tg2);
    }
void sub2(){
    dfs(1,0);
    Build(1,1,n);
    for(int i=1;i<=m;i++){
        int x=tv[i].id,u=tv[i].u;
        if(x==1){
            node res=Find(1,1,n,1,n);
            if(res.i==0) res.val=-1;
            cout<<res.val<<'\n';
        }
        else if(x==2){
            Upd2(1,1,n,i_in[u]);
        }
        else {
            int v=tv[i].v;
            ll W=tv[i].w;
            int j=g[u][v];
            if(u==pa[v]) swap(u,v);
            Update(1,1,n,in[u],out[u],w[j]-W);
            w[j]=W;
        }
    }
    }
void tinh(){
    cin>>n>>m;
    //for(int i=1;i<=n;i++) ans[i]=mod;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v>>w[i];
        adj[u].pu({v,i});
        adj[v].pu({u,i});
        g[u][v]=i;
        g[v][u]=i;
    }
    if(n<=2000 and m<=2000) {
        sub1();
        return;
    }
    int cnt1=0,cnt=0;
    for(int i=1;i<=m;i++){
        cin>>tv[i].id>>tv[i].u;
        if(tv[i].id==3) cin>>tv[i].v>>tv[i].w;
        if(tv[i].id==1){
            cnt1++;
            if(tv[i].u==1) cnt++;
        }
    }

    if(cnt1==cnt){
        sub2();
        return;
    }
    }
int main(){
    //freopen("jday.inp","r",stdin);
    //freopen("jday.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    tinh();
    return 0;

}
//code của anh Nam đẹp trai nhất CHL

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