oj.uz

Submission #1111798

# Submission time Handle Problem Language Result Execution time Memory
1111798 2024-11-13T00:54:11 Z Tai_xiu Grapevine (NOI22_grapevine) C++17
53 / 100
 1868 ms 278176 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define i128 int128
#define ii pair<int,int>
#define ld long double
#define vi vector<int>
#define vvi vector<vi>
#define vii vector<pair<int,int>>
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FOR1(i,a,b,c) for (int i=a;i<=b;i+=c)
#define REP(i,a,b) for (int i=a;i>=b;i--)
#define REP1(i,a,b,c) for(int i=b;i>=a;i-=c)
#define endh '\n';
#define len(a) a.length()
#define pb(c) push_back(c)
#define elif else if
#define ppb() pop_back()
#define rong std::npos
#define all(c) (c.begin(),c.end())
#define Z int
#define R double
#define lcm(a,b) ((int) (a/__gcd(a,b))*b)
#define mk(a,b) make_pair(a,b)
Z dx4[]={-1,1,0,0};
Z dy4[]={0,0,1,-1};
string co="YES",khong="NO";
const int mod=1e9+7;
const Z maxn=100005;
const Z oo=1e17;
Z sz[maxn],tin[20][maxn],tout[20][maxn],vis[maxn],id[maxn],n,par[maxn],q,h[maxn],have[maxn];
vi g[maxn];
map<Z,Z>mp[maxn];
Z ew[maxn];
ii canh[maxn];
struct segtree
{
    vi st,lazy;
    segtree(){}
    segtree(Z _n,Z _val){
        st=vi(4*_n+7,_val);
        lazy=vi(4*_n+7);
    }
    void push(Z v)
    {
        st[v*2]+=lazy[v];
        st[v*2+1]+=lazy[v];
        lazy[v*2]+=lazy[v];
        lazy[v*2+1]+=lazy[v];
        lazy[v]=0;
    }
  void update(Z v,Z tl,Z tr,Z l,Z r,Z val)
  {
      if (tl>tr || l>r || tl>r || tr<l) return;
        if (tl>=l && tr<=r){
            st[v]+=val;
            lazy[v]+=val;
            return;
        }
        Z tm=tl+tr>>1;
        push(v);
        update(v*2,tl,tm,l,r,val);
        update(v*2+1,tm+1,tr,l,r,val);
        st[v]=min(st[v*2],st[v*2+1]);
  }
   void change(Z v,Z tl,Z tr,Z pos,Z val)
  {
        if (tl==tr) {
            st[v]=val;
            return;
        }
        push(v);
        Z tm=tl+tr>>1;
        if (pos<=tm) change(v*2,tl,tm,pos,val);
        else change(v*2+1,tm+1,tr,pos,val);
        st[v]=min(st[v*2],st[v*2+1]);
  }
  Z query(Z v,Z tl,Z tr,Z l,Z r)
  {
      if (tl>tr || l>r || tl>r || tr<l) return oo;
      if (tl>=l && tr<=r) return st[v];
      push(v);
      Z tm=(tl+tr)>>1;
      return min(query(v*2,tl,tm,l,r),query(v*2+1,tm+1,tr,l,r));
  }
}st1[maxn],st2[maxn];
Z getsize(Z u,Z p)
{
    sz[u]=1;
//    cout<<u<<endl;
    for (Z v:g[u]){
        if (vis[v] || v==p) continue;
        sz[u]+=getsize(v,u);
    }
    return sz[u];
}
Z centroid (Z u,Z p,Z sai)
{
//    cout<<u<<endl;
    for (Z v:g[u]){
        if (sz[v]>sai/2 && !vis[v] && v!=p) return centroid(v,u,sai);
    }
    return u;
}
void dfs(Z u,Z p,Z depth,Z root)
{
    tin[depth][u]=++id[root];
    for (Z v:g[u]){
        if (v!=p && !vis[v]) dfs(v,u,depth,root);
    }
    tout[depth][u]=id[root];
}
void decomp(Z u,Z p,Z depth)
{
    Z c=centroid(u,u,getsize(u,u));
    vis[c]=1;
    par[c]=p;
    st1[c]=segtree(sz[u],0);
    st2[c]=segtree(sz[u],oo);
    h[c]=depth;
//    cout<<c<<" "<<depth<<'\n';
    dfs(c,-1,depth,c);
    for (Z v:g[c]) if (!vis[v]) decomp(v,c,depth+1);
}
void anneal(Z u,Z v,Z w)
{
    if (h[u]>h[v]) swap(u,v);
    Z node=u;
    REP(i,h[u],0){
        Z curr=(tin[i][u]<tin[i][v])?v:u;
        st1[node].update(1,1,id[node],tin[i][curr],tout[i][curr],w);
        st2[node].update(1,1,id[node],tin[i][curr],tout[i][curr],w);
        node=par[node];
    }
}
void soak(Z u)
{
    have[u]^=1;
    Z node=u;
    REP(i,h[u],0){
//        cout<<node<<" "<<" "<<st1[node].query(1,1,id[node],tin[i][u],tin[i][u])<<" ??\n";

        if (!have[u]) st2[node].change(1,1,id[node],tin[i][u],oo);
        else st2[node].change(1,1,id[node],tin[i][u],st1[node].query(1,1,id[node],tin[i][u],tin[i][u]));
        node=par[node];
    }
}
void seek(Z u)
{
    Z ans=oo;
    Z node=u;
    REP(i,h[u],0){
       ans=min(ans,st1[node].query(1,1,id[node],tin[i][u],tin[i][u])+st2[node].st[1]);
       node=par[node];
    }
    if (ans>=oo) cout<<-1<<'\n';
    else cout<<ans<<'\n';
}
/*
7 2
1 2 2
2 3 4
5 6 1
5 3 6
3 7 6
2 4 9
2 3
1 1


*/
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>q;
    FOR(i,1,n-1){
        cin>>canh[i].first>>canh[i].second>>ew[i];
        if (canh[i].first>canh[i].second) swap(canh[i].first,canh[i].second);
        mp[canh[i].first][canh[i].second]=i;
        g[canh[i].first].pb(canh[i].second);
        g[canh[i].second].pb(canh[i].first);

    }
    decomp(1,-1,0);
    FOR(i,1,n-1)
    {
        anneal(canh[i].first,canh[i].second,ew[mp[canh[i].first][canh[i].second]]);
    }
    while(q--){
        Z type;
        cin>>type;
        if (type==1) {
            Z u; cin>>u; seek(u);
        }
        else if (type==2){
            Z u; cin>>u; soak(u);
        }
        else {
            Z u,v,w; cin>>u>>v>>w;
            if (u>v) swap(u,v);
            anneal(u,v,w-ew[mp[u][v]]);
           ew[ mp[u][v]]=w;
        }
    }
//    FOR(i,0,2){
//        FOR(j,1,n) cout<<tin[i][j]<<" ";
//        cout<<'\n';
//        FOR(j,1,n) cout<<tout[i][j]<<" ";
//        cout<<'\n';
//        cout<<"////\n";
//    }
//    FOR(i,1,3) cout<<id[node]<<" ";
}

Compilation message

Main.cpp: In member function 'void segtree::update(long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:61:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |         Z tm=tl+tr>>1;
      |              ~~^~~
Main.cpp: In member function 'void segtree::change(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:74:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         Z tm=tl+tr>>1;
      |              ~~^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 44368 KB Output is correct
2 Correct 14 ms 44112 KB Output is correct
3 Correct 14 ms 44368 KB Output is correct
4 Correct 14 ms 44624 KB Output is correct
5 Correct 14 ms 44624 KB Output is correct
6 Correct 14 ms 44556 KB Output is correct
7 Correct 7 ms 30544 KB Output is correct
8 Correct 7 ms 28496 KB Output is correct
9 Correct 7 ms 30592 KB Output is correct
10 Correct 13 ms 44624 KB Output is correct
11 Correct 15 ms 44624 KB Output is correct
12 Correct 13 ms 44368 KB Output is correct
13 Correct 8 ms 30544 KB Output is correct
14 Correct 8 ms 30544 KB Output is correct
15 Correct 8 ms 30544 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1505 ms 235072 KB Output is correct
2 Correct 1613 ms 226536 KB Output is correct
3 Correct 1635 ms 231556 KB Output is correct
4 Correct 1323 ms 276808 KB Output is correct
5 Correct 1166 ms 261976 KB Output is correct
6 Correct 1183 ms 263888 KB Output is correct
7 Correct 189 ms 90044 KB Output is correct
8 Correct 213 ms 88508 KB Output is correct
9 Correct 226 ms 88764 KB Output is correct
10 Correct 1313 ms 273336 KB Output is correct
11 Correct 1251 ms 269260 KB Output is correct
12 Correct 1312 ms 278176 KB Output is correct
13 Correct 210 ms 86468 KB Output is correct
14 Correct 245 ms 86460 KB Output is correct
15 Correct 230 ms 89532 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1376 ms 268872 KB Output is correct
2 Correct 1300 ms 266908 KB Output is correct
3 Correct 1378 ms 270812 KB Output is correct
4 Correct 1362 ms 264372 KB Output is correct
5 Correct 1466 ms 266188 KB Output is correct
6 Correct 1458 ms 262728 KB Output is correct
7 Correct 1260 ms 262824 KB Output is correct
8 Correct 1285 ms 267848 KB Output is correct
9 Correct 1279 ms 263828 KB Output is correct
10 Correct 1396 ms 270392 KB Output is correct
11 Correct 1348 ms 264292 KB Output is correct
12 Correct 1487 ms 260936 KB Output is correct
13 Correct 1440 ms 267592 KB Output is correct
14 Correct 1248 ms 263844 KB Output is correct
15 Correct 1268 ms 264796 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1544 ms 231136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1868 ms 237728 KB Output is correct
2 Correct 1713 ms 236016 KB Output is correct
3 Correct 1648 ms 230264 KB Output is correct
4 Correct 1349 ms 265288 KB Output is correct
5 Correct 1336 ms 266400 KB Output is correct
6 Correct 1530 ms 266956 KB Output is correct
7 Correct 242 ms 90556 KB Output is correct
8 Correct 252 ms 88764 KB Output is correct
9 Correct 267 ms 89276 KB Output is correct
10 Correct 1427 ms 257148 KB Output is correct
11 Correct 1494 ms 265224 KB Output is correct
12 Correct 1470 ms 268084 KB Output is correct
13 Correct 225 ms 91836 KB Output is correct
14 Correct 231 ms 87996 KB Output is correct
15 Correct 196 ms 90820 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 44368 KB Output is correct
2 Correct 14 ms 44112 KB Output is correct
3 Correct 14 ms 44368 KB Output is correct
4 Correct 14 ms 44624 KB Output is correct
5 Correct 14 ms 44624 KB Output is correct
6 Correct 14 ms 44556 KB Output is correct
7 Correct 7 ms 30544 KB Output is correct
8 Correct 7 ms 28496 KB Output is correct
9 Correct 7 ms 30592 KB Output is correct
10 Correct 13 ms 44624 KB Output is correct
11 Correct 15 ms 44624 KB Output is correct
12 Correct 13 ms 44368 KB Output is correct
13 Correct 8 ms 30544 KB Output is correct
14 Correct 8 ms 30544 KB Output is correct
15 Correct 8 ms 30544 KB Output is correct
16 Correct 1505 ms 235072 KB Output is correct
17 Correct 1613 ms 226536 KB Output is correct
18 Correct 1635 ms 231556 KB Output is correct
19 Correct 1323 ms 276808 KB Output is correct
20 Correct 1166 ms 261976 KB Output is correct
21 Correct 1183 ms 263888 KB Output is correct
22 Correct 189 ms 90044 KB Output is correct
23 Correct 213 ms 88508 KB Output is correct
24 Correct 226 ms 88764 KB Output is correct
25 Correct 1313 ms 273336 KB Output is correct
26 Correct 1251 ms 269260 KB Output is correct
27 Correct 1312 ms 278176 KB Output is correct
28 Correct 210 ms 86468 KB Output is correct
29 Correct 245 ms 86460 KB Output is correct
30 Correct 230 ms 89532 KB Output is correct
31 Correct 1376 ms 268872 KB Output is correct
32 Correct 1300 ms 266908 KB Output is correct
33 Correct 1378 ms 270812 KB Output is correct
34 Correct 1362 ms 264372 KB Output is correct
35 Correct 1466 ms 266188 KB Output is correct
36 Correct 1458 ms 262728 KB Output is correct
37 Correct 1260 ms 262824 KB Output is correct
38 Correct 1285 ms 267848 KB Output is correct
39 Correct 1279 ms 263828 KB Output is correct
40 Correct 1396 ms 270392 KB Output is correct
41 Correct 1348 ms 264292 KB Output is correct
42 Correct 1487 ms 260936 KB Output is correct
43 Correct 1440 ms 267592 KB Output is correct
44 Correct 1248 ms 263844 KB Output is correct
45 Correct 1268 ms 264796 KB Output is correct
46 Incorrect 1544 ms 231136 KB Output isn't correct
47 Halted 0 ms 0 KB -