oj.uz

답안 #1111796

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1111796 2024-11-13T00:49:43 Z Tai_xiu Grapevine (NOI22_grapevine) C++17
53 / 100
 1909 ms 280628 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=1e15;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 28240 KB Output is correct
2 Correct 12 ms 27984 KB Output is correct
3 Correct 15 ms 24400 KB Output is correct
4 Correct 14 ms 23632 KB Output is correct
5 Correct 18 ms 23376 KB Output is correct
6 Correct 14 ms 24656 KB Output is correct
7 Correct 10 ms 21456 KB Output is correct
8 Correct 10 ms 21328 KB Output is correct
9 Correct 14 ms 21584 KB Output is correct
10 Correct 16 ms 24668 KB Output is correct
11 Correct 15 ms 23632 KB Output is correct
12 Correct 19 ms 23376 KB Output is correct
13 Correct 16 ms 18256 KB Output is correct
14 Correct 12 ms 18256 KB Output is correct
15 Correct 12 ms 21588 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1444 ms 234296 KB Output is correct
2 Correct 1623 ms 229740 KB Output is correct
3 Correct 1508 ms 228812 KB Output is correct
4 Correct 1391 ms 277076 KB Output is correct
5 Correct 1403 ms 262716 KB Output is correct
6 Correct 1302 ms 265544 KB Output is correct
7 Correct 195 ms 91880 KB Output is correct
8 Correct 194 ms 90132 KB Output is correct
9 Correct 202 ms 89020 KB Output is correct
10 Correct 1257 ms 275312 KB Output is correct
11 Correct 1346 ms 271132 KB Output is correct
12 Correct 1357 ms 280628 KB Output is correct
13 Correct 204 ms 90556 KB Output is correct
14 Correct 223 ms 89364 KB Output is correct
15 Correct 242 ms 90204 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1328 ms 268992 KB Output is correct
2 Correct 1389 ms 272164 KB Output is correct
3 Correct 1522 ms 270960 KB Output is correct
4 Correct 1540 ms 264108 KB Output is correct
5 Correct 1515 ms 266148 KB Output is correct
6 Correct 1562 ms 264868 KB Output is correct
7 Correct 1460 ms 262216 KB Output is correct
8 Correct 1534 ms 267820 KB Output is correct
9 Correct 1558 ms 263344 KB Output is correct
10 Correct 1346 ms 272360 KB Output is correct
11 Correct 1450 ms 264520 KB Output is correct
12 Correct 1545 ms 260684 KB Output is correct
13 Correct 1509 ms 267848 KB Output is correct
14 Correct 1478 ms 260424 KB Output is correct
15 Correct 1484 ms 264492 KB Output is correct

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1674 ms 231492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1909 ms 237928 KB Output is correct
2 Correct 1747 ms 236600 KB Output is correct
3 Correct 1721 ms 231496 KB Output is correct
4 Correct 1501 ms 262472 KB Output is correct
5 Correct 1359 ms 267356 KB Output is correct
6 Correct 1545 ms 269864 KB Output is correct
7 Correct 233 ms 93292 KB Output is correct
8 Correct 247 ms 94140 KB Output is correct
9 Correct 266 ms 94396 KB Output is correct
10 Correct 1482 ms 260564 KB Output is correct
11 Correct 1511 ms 268360 KB Output is correct
12 Correct 1378 ms 269788 KB Output is correct
13 Correct 237 ms 90556 KB Output is correct
14 Correct 201 ms 90888 KB Output is correct
15 Correct 207 ms 89460 KB Output is correct

Subtask #6
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 28240 KB Output is correct
2 Correct 12 ms 27984 KB Output is correct
3 Correct 15 ms 24400 KB Output is correct
4 Correct 14 ms 23632 KB Output is correct
5 Correct 18 ms 23376 KB Output is correct
6 Correct 14 ms 24656 KB Output is correct
7 Correct 10 ms 21456 KB Output is correct
8 Correct 10 ms 21328 KB Output is correct
9 Correct 14 ms 21584 KB Output is correct
10 Correct 16 ms 24668 KB Output is correct
11 Correct 15 ms 23632 KB Output is correct
12 Correct 19 ms 23376 KB Output is correct
13 Correct 16 ms 18256 KB Output is correct
14 Correct 12 ms 18256 KB Output is correct
15 Correct 12 ms 21588 KB Output is correct
16 Correct 1444 ms 234296 KB Output is correct
17 Correct 1623 ms 229740 KB Output is correct
18 Correct 1508 ms 228812 KB Output is correct
19 Correct 1391 ms 277076 KB Output is correct
20 Correct 1403 ms 262716 KB Output is correct
21 Correct 1302 ms 265544 KB Output is correct
22 Correct 195 ms 91880 KB Output is correct
23 Correct 194 ms 90132 KB Output is correct
24 Correct 202 ms 89020 KB Output is correct
25 Correct 1257 ms 275312 KB Output is correct
26 Correct 1346 ms 271132 KB Output is correct
27 Correct 1357 ms 280628 KB Output is correct
28 Correct 204 ms 90556 KB Output is correct
29 Correct 223 ms 89364 KB Output is correct
30 Correct 242 ms 90204 KB Output is correct
31 Correct 1328 ms 268992 KB Output is correct
32 Correct 1389 ms 272164 KB Output is correct
33 Correct 1522 ms 270960 KB Output is correct
34 Correct 1540 ms 264108 KB Output is correct
35 Correct 1515 ms 266148 KB Output is correct
36 Correct 1562 ms 264868 KB Output is correct
37 Correct 1460 ms 262216 KB Output is correct
38 Correct 1534 ms 267820 KB Output is correct
39 Correct 1558 ms 263344 KB Output is correct
40 Correct 1346 ms 272360 KB Output is correct
41 Correct 1450 ms 264520 KB Output is correct
42 Correct 1545 ms 260684 KB Output is correct
43 Correct 1509 ms 267848 KB Output is correct
44 Correct 1478 ms 260424 KB Output is correct
45 Correct 1484 ms 264492 KB Output is correct
46 Incorrect 1674 ms 231492 KB Output isn't correct
47 Halted 0 ms 0 KB -