oj.uz

Submission #1111433

# Submission time Handle Problem Language Result Execution time Memory
1111433 2024-11-12T08:25:52 Z KawakiMeido Synchronization (JOI13_synchronization) C++17
100 / 100
 1082 ms 29288 KB 
/*Author: KawakiMeido*/
#include <bits/stdc++.h>
#define pb push_back
#define endl "\n"
#define ll long long
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pib pair<int,bool>
#define piib pair<pii,bool>
#define fi first
#define se second

using namespace std;

/*Constants*/
const int N = 2e5+10;
const int INF = 1e9+7;
const long long LLINF = 1e18+3;

/*TestCases*/
int test=1;
void solve();
void TestCases(bool v){
    if (v) cin >> test;
    while(test--) solve();
}

/*Global Variables*/
int n,m,q;
vector<pii> adj[N];
bool state[N];
int residue[N];
pii edge[N];

piib Comb(piib x, piib y){
    if (x.fi.fi == -INF) return y;
    if (y.fi.fi == -INF) return x;

    return make_pair( make_pair(((y.se)? x.fi.fi : y.fi.fi), ((y.se)? x.fi.se: y.fi.se)) ,(x.se&&y.se));
}

struct SegTree{
    int n;
    vector<piib> ST;

    void Build_Rec(int idx, int l, int r){
        if (l==r){
            ST[idx] = {{1,l},false};
            return;
        }
        int mid = (l+r)/2;
        Build_Rec(idx*2,l,mid); Build_Rec(idx*2+1,mid+1,r);
        ST[idx] = Comb(ST[idx*2],ST[idx*2+1]);
    }

    void Build(int _n){
        n = _n;
        ST.resize(4*n+10);
        Build_Rec(1,1,n);
    }

    void UpdateState(int idx, int l, int r, int x, bool val){
        if (x<l || r<x) return;
        if (l==r){
            ST[idx].se = val;
            return;
        }
        int mid = (l+r)/2;
        UpdateState(idx*2,l,mid,x,val); UpdateState(idx*2+1,mid+1,r,x,val);
        ST[idx] = Comb(ST[idx*2],ST[idx*2+1]);
    }

    void UpdateVal(int idx, int l, int r, int x, int val){
        if (x<l || r<x) return;
        if (l==r){
            ST[idx].fi.fi = val;
            return;
        }
        int mid = (l+r)/2;
        UpdateVal(idx*2,l,mid,x,val); UpdateVal(idx*2+1,mid+1,r,x,val);
        ST[idx] = Comb(ST[idx*2],ST[idx*2+1]);
    }

    piib Get(int idx, int l, int r, int x, int y){
        if (y<l || r<x) return make_pair(make_pair(-INF,0),0);
        if (x<=l && r<=y) return ST[idx];
        int mid = (l+r)/2;
        return Comb(Get(idx*2,l,mid,x,y),Get(idx*2+1,mid+1,r,x,y));
    }
} ST;

//HLD
int curpos = 0;
int parent[N],sz[N],depth[N];
int root[N],pos[N];

void DFS(int u, int p, int id){
    edge[id] = {u,p};
    sz[u] = 1;
    for (auto &in:adj[u]){
        int v,vid; tie(v,vid) = in;
        if (v==p) continue;
        parent[v] = u;
        depth[v] = depth[u]+1;
        DFS(v,u,vid);
        sz[u]+=sz[v];
    }
}

void HLD(int u, int r){
    root[u] = r;
    pos[u] = ++curpos;

    int nxt = 0;
    for (auto &in:adj[u]){
        int v = in.fi;
        if (v==parent[u]) continue;
        if (!nxt || sz[nxt]<sz[v]) nxt = v;
    }
    if (nxt) HLD(nxt,r);
    for (auto &in:adj[u]){
        int v = in.fi;
        if (v==parent[u] || v==nxt) continue;
        HLD(v,v);
    }
}

piib Query(int u){
    piib res = {{-INF,0},0};
    while (root[u]!=1){
        res = Comb(ST.Get(1,1,n,pos[root[u]],pos[u]),res);
        u = parent[root[u]];
    }
    res = Comb(ST.Get(1,1,n,pos[1],pos[u]),res);
    return res;
}

void Update(int id){
    if (!state[id]){
        piib res1 = Query(edge[id].fi);
        piib res2 = Query(edge[id].se);
        int val = res1.fi.fi+res2.fi.fi-residue[id];
        ST.UpdateState(1,1,n,pos[edge[id].fi],true);
        ST.UpdateVal(1,1,n,res2.fi.se,val);
    }
    else{
        piib res1 = Query(edge[id].fi);
        int val = res1.fi.fi;
        ST.UpdateState(1,1,n,pos[edge[id].fi],false);
        ST.UpdateVal(1,1,n,pos[edge[id].fi],val);
        residue[id] = val;
    }
    state[id] = !state[id];
}

/*Solution*/
void solve(){
    cin >> n >> m >> q;
    for (int i=1; i<n; i++){
        int u,v; cin >> u >> v;
        adj[u].push_back({v,i});
        adj[v].push_back({u,i});
    }
    ST.Build(n);
    DFS(1,0,0);
    HLD(1,1);
    for (int i=1; i<=m; i++){
        int x; cin >> x;
        Update(x);
    }
    for (int i=1; i<=q; i++){
        int x; cin >> x;
        piib res = Query(x);
        cout << res.fi.fi << endl;
    }
}

/*Driver Code*/
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    TestCases(0);

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7248 KB Output is correct
2 Correct 2 ms 7248 KB Output is correct
3 Correct 2 ms 7248 KB Output is correct
4 Correct 2 ms 7248 KB Output is correct
5 Correct 2 ms 7248 KB Output is correct
6 Correct 6 ms 7248 KB Output is correct
7 Correct 59 ms 8528 KB Output is correct
8 Correct 59 ms 8528 KB Output is correct
9 Correct 58 ms 8528 KB Output is correct
10 Correct 814 ms 21188 KB Output is correct
11 Correct 861 ms 21064 KB Output is correct
12 Correct 345 ms 28488 KB Output is correct
13 Correct 368 ms 20900 KB Output is correct
14 Correct 485 ms 20716 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 24516 KB Output is correct
2 Correct 315 ms 24332 KB Output is correct
3 Correct 200 ms 27784 KB Output is correct
4 Correct 195 ms 27720 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7248 KB Output is correct
2 Correct 2 ms 7248 KB Output is correct
3 Correct 2 ms 7248 KB Output is correct
4 Correct 2 ms 7248 KB Output is correct
5 Correct 3 ms 7352 KB Output is correct
6 Correct 4 ms 7504 KB Output is correct
7 Correct 33 ms 9340 KB Output is correct
8 Correct 412 ms 29256 KB Output is correct
9 Correct 417 ms 29256 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 29256 KB Output is correct
2 Correct 245 ms 28784 KB Output is correct
3 Correct 247 ms 29000 KB Output is correct
4 Correct 240 ms 29000 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7248 KB Output is correct
3 Correct 2 ms 7248 KB Output is correct
4 Correct 2 ms 7248 KB Output is correct
5 Correct 7 ms 7496 KB Output is correct
6 Correct 78 ms 8528 KB Output is correct
7 Correct 1082 ms 22076 KB Output is correct
8 Correct 389 ms 29288 KB Output is correct
9 Correct 461 ms 22220 KB Output is correct
10 Correct 665 ms 21948 KB Output is correct
11 Correct 348 ms 25796 KB Output is correct
12 Correct 349 ms 25912 KB Output is correct
13 Correct 232 ms 29000 KB Output is correct