oj.uz

Submission #1111799

# Submission time Handle Problem Language Result Execution time Memory
1111799 2024-11-13T00:56:19 Z Tai_xiu Grapevine (NOI22_grapevine) C++14
100 / 100
 1756 ms 279480 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>=1e14) 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 17 ms 44368 KB Output is correct
2 Correct 15 ms 44112 KB Output is correct
3 Correct 17 ms 44112 KB Output is correct
4 Correct 14 ms 44624 KB Output is correct
5 Correct 14 ms 42320 KB Output is correct
6 Correct 16 ms 44624 KB Output is correct
7 Correct 7 ms 30712 KB Output is correct
8 Correct 9 ms 30544 KB Output is correct
9 Correct 9 ms 30336 KB Output is correct
10 Correct 14 ms 38648 KB Output is correct
11 Correct 15 ms 40536 KB Output is correct
12 Correct 17 ms 34384 KB Output is correct
13 Correct 9 ms 30544 KB Output is correct
14 Correct 10 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 1438 ms 232264 KB Output is correct
2 Correct 1317 ms 226632 KB Output is correct
3 Correct 1511 ms 225596 KB Output is correct
4 Correct 1387 ms 273816 KB Output is correct
5 Correct 1225 ms 259308 KB Output is correct
6 Correct 1346 ms 262464 KB Output is correct
7 Correct 213 ms 91836 KB Output is correct
8 Correct 228 ms 91500 KB Output is correct
9 Correct 228 ms 90336 KB Output is correct
10 Correct 1368 ms 273392 KB Output is correct
11 Correct 1168 ms 268744 KB Output is correct
12 Correct 1226 ms 277572 KB Output is correct
13 Correct 190 ms 87932 KB Output is correct
14 Correct 196 ms 86460 KB Output is correct
15 Correct 235 ms 87512 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1529 ms 266876 KB Output is correct
2 Correct 1549 ms 268280 KB Output is correct
3 Correct 1575 ms 268852 KB Output is correct
4 Correct 1437 ms 262228 KB Output is correct
5 Correct 1309 ms 264140 KB Output is correct
6 Correct 1276 ms 261268 KB Output is correct
7 Correct 1383 ms 260604 KB Output is correct
8 Correct 1496 ms 265876 KB Output is correct
9 Correct 1418 ms 262216 KB Output is correct
10 Correct 1499 ms 269640 KB Output is correct
11 Correct 1385 ms 263744 KB Output is correct
12 Correct 1403 ms 259048 KB Output is correct
13 Correct 1419 ms 265860 KB Output is correct
14 Correct 1442 ms 260724 KB Output is correct
15 Correct 1476 ms 262576 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1736 ms 229284 KB Output is correct
2 Correct 1578 ms 235116 KB Output is correct
3 Correct 1411 ms 226120 KB Output is correct
4 Correct 1419 ms 277128 KB Output is correct
5 Correct 1487 ms 273880 KB Output is correct
6 Correct 1506 ms 279480 KB Output is correct
7 Correct 233 ms 93628 KB Output is correct
8 Correct 238 ms 95420 KB Output is correct
9 Correct 251 ms 93884 KB Output is correct
10 Correct 1463 ms 274504 KB Output is correct
11 Correct 1206 ms 265324 KB Output is correct
12 Correct 1289 ms 274268 KB Output is correct
13 Correct 219 ms 90812 KB Output is correct
14 Correct 205 ms 91588 KB Output is correct
15 Correct 200 ms 90300 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1756 ms 235776 KB Output is correct
2 Correct 1681 ms 233288 KB Output is correct
3 Correct 1634 ms 227000 KB Output is correct
4 Correct 1316 ms 259656 KB Output is correct
5 Correct 1289 ms 264408 KB Output is correct
6 Correct 1284 ms 266928 KB Output is correct
7 Correct 229 ms 88764 KB Output is correct
8 Correct 231 ms 88764 KB Output is correct
9 Correct 235 ms 87996 KB Output is correct
10 Correct 1413 ms 255736 KB Output is correct
11 Correct 1485 ms 265352 KB Output is correct
12 Correct 1460 ms 268260 KB Output is correct
13 Correct 233 ms 91800 KB Output is correct
14 Correct 239 ms 88072 KB Output is correct
15 Correct 224 ms 86892 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 44368 KB Output is correct
2 Correct 15 ms 44112 KB Output is correct
3 Correct 17 ms 44112 KB Output is correct
4 Correct 14 ms 44624 KB Output is correct
5 Correct 14 ms 42320 KB Output is correct
6 Correct 16 ms 44624 KB Output is correct
7 Correct 7 ms 30712 KB Output is correct
8 Correct 9 ms 30544 KB Output is correct
9 Correct 9 ms 30336 KB Output is correct
10 Correct 14 ms 38648 KB Output is correct
11 Correct 15 ms 40536 KB Output is correct
12 Correct 17 ms 34384 KB Output is correct
13 Correct 9 ms 30544 KB Output is correct
14 Correct 10 ms 30544 KB Output is correct
15 Correct 8 ms 30544 KB Output is correct
16 Correct 1438 ms 232264 KB Output is correct
17 Correct 1317 ms 226632 KB Output is correct
18 Correct 1511 ms 225596 KB Output is correct
19 Correct 1387 ms 273816 KB Output is correct
20 Correct 1225 ms 259308 KB Output is correct
21 Correct 1346 ms 262464 KB Output is correct
22 Correct 213 ms 91836 KB Output is correct
23 Correct 228 ms 91500 KB Output is correct
24 Correct 228 ms 90336 KB Output is correct
25 Correct 1368 ms 273392 KB Output is correct
26 Correct 1168 ms 268744 KB Output is correct
27 Correct 1226 ms 277572 KB Output is correct
28 Correct 190 ms 87932 KB Output is correct
29 Correct 196 ms 86460 KB Output is correct
30 Correct 235 ms 87512 KB Output is correct
31 Correct 1529 ms 266876 KB Output is correct
32 Correct 1549 ms 268280 KB Output is correct
33 Correct 1575 ms 268852 KB Output is correct
34 Correct 1437 ms 262228 KB Output is correct
35 Correct 1309 ms 264140 KB Output is correct
36 Correct 1276 ms 261268 KB Output is correct
37 Correct 1383 ms 260604 KB Output is correct
38 Correct 1496 ms 265876 KB Output is correct
39 Correct 1418 ms 262216 KB Output is correct
40 Correct 1499 ms 269640 KB Output is correct
41 Correct 1385 ms 263744 KB Output is correct
42 Correct 1403 ms 259048 KB Output is correct
43 Correct 1419 ms 265860 KB Output is correct
44 Correct 1442 ms 260724 KB Output is correct
45 Correct 1476 ms 262576 KB Output is correct
46 Correct 1736 ms 229284 KB Output is correct
47 Correct 1578 ms 235116 KB Output is correct
48 Correct 1411 ms 226120 KB Output is correct
49 Correct 1419 ms 277128 KB Output is correct
50 Correct 1487 ms 273880 KB Output is correct
51 Correct 1506 ms 279480 KB Output is correct
52 Correct 233 ms 93628 KB Output is correct
53 Correct 238 ms 95420 KB Output is correct
54 Correct 251 ms 93884 KB Output is correct
55 Correct 1463 ms 274504 KB Output is correct
56 Correct 1206 ms 265324 KB Output is correct
57 Correct 1289 ms 274268 KB Output is correct
58 Correct 219 ms 90812 KB Output is correct
59 Correct 205 ms 91588 KB Output is correct
60 Correct 200 ms 90300 KB Output is correct
61 Correct 1756 ms 235776 KB Output is correct
62 Correct 1681 ms 233288 KB Output is correct
63 Correct 1634 ms 227000 KB Output is correct
64 Correct 1316 ms 259656 KB Output is correct
65 Correct 1289 ms 264408 KB Output is correct
66 Correct 1284 ms 266928 KB Output is correct
67 Correct 229 ms 88764 KB Output is correct
68 Correct 231 ms 88764 KB Output is correct
69 Correct 235 ms 87996 KB Output is correct
70 Correct 1413 ms 255736 KB Output is correct
71 Correct 1485 ms 265352 KB Output is correct
72 Correct 1460 ms 268260 KB Output is correct
73 Correct 233 ms 91800 KB Output is correct
74 Correct 239 ms 88072 KB Output is correct
75 Correct 224 ms 86892 KB Output is correct
76 Correct 4 ms 21156 KB Output is correct
77 Correct 6 ms 21072 KB Output is correct
78 Correct 7 ms 20048 KB Output is correct
79 Correct 1532 ms 227144 KB Output is correct
80 Correct 1441 ms 232264 KB Output is correct
81 Correct 1607 ms 235224 KB Output is correct
82 Correct 1368 ms 269328 KB Output is correct
83 Correct 1379 ms 266312 KB Output is correct
84 Correct 1433 ms 268872 KB Output is correct
85 Correct 275 ms 93704 KB Output is correct
86 Correct 248 ms 92348 KB Output is correct
87 Correct 230 ms 93372 KB Output is correct
88 Correct 1395 ms 264516 KB Output is correct
89 Correct 1395 ms 268232 KB Output is correct
90 Correct 1381 ms 266916 KB Output is correct
91 Correct 232 ms 91580 KB Output is correct
92 Correct 233 ms 90044 KB Output is correct
93 Correct 241 ms 89532 KB Output is correct