oj.uz

Submission #1112296

# Submission time Handle Problem Language Result Execution time Memory
1112296 2024-11-14T03:02:28 Z KawakiMeido Cats or Dogs (JOI18_catdog) C++17
38 / 100
 3000 ms 46152 KB 
/*Author: KawakiMeido*/
#include <bits/stdc++.h>
#define pb push_back
#define endl "\n"
#define ll long long
#define int long long
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;

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

/*Global Variables*/
int n;
vector<int> adj[N];
int pre[N];

struct Node{
    vector<int> val;
    Node(){
        val.resize(4,LLINF);
    }
    int mn(){
        return min({val[0],val[1],val[2],val[3]});
    }
};

Node Comb(Node x, Node y){
    Node res;
    if (x.val[0] == LLINF) return y;
    if (y.val[0] == LLINF) return x;
    for (int i=0; i<4; i++){
        for (int j=0; j<4; j++){
            int idx = (i&(1<<1)) + (j&1);
            int val = x.val[i] + y.val[j] + (((i&1)^((j>>1)&1))?1:0);
            res.val[idx] = min(res.val[idx],val);
        }
    }
    return res;
}

struct SegTree{

    int n;
    vector<Node> ST;

    void Build_Rec(int idx, int l, int r){
        if (l==r){
            ST[idx].val[0] = ST[idx].val[3] = 0;
            ST[idx].val[1] = ST[idx].val[2] = INF;
            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 Update(int idx, int l, int r, int x, int val, int state){
        if (x<l || r<x) return;
        if (l==r){
            ST[idx].val[3*state] += val;
            return;
        }

        int mid = (l+r)/2;
        Update(idx*2,l,mid,x,val,state); Update(idx*2+1,mid+1,r,x,val,state);
        ST[idx] = Comb(ST[idx*2],ST[idx*2+1]);
    }

    Node Get(int idx, int l, int r, int x, int y){
        if (y<l || r<x) return Node();
        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];
int tin[N],tout[N];
vector<vector<int>> residue(N,vector<int>(2,0));

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

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

    int nxt = 0;
    for (auto v:adj[u]){
        if (v==parent[u]) continue;
        if (!nxt || sz[nxt]<sz[v]) nxt = v;
    }

    if (nxt) HLD(nxt,r);
    else tout[r] = curpos;

    for (auto v:adj[u]){
        if (v==parent[u] || v==nxt) continue;
        HLD(v,v);
    }
}


Node CBT(int x){
    while (root[x]!=1){
        Node tmp = ST.Get(1,1,n,tin[root[x]],tout[root[x]]);
        int p = parent[root[x]];
        ST.Update(1,1,n,pos[p],-residue[root[x]][0],0);
        ST.Update(1,1,n,pos[p],-residue[root[x]][1],1);
        residue[root[x]][0] = min({tmp.val[0],tmp.val[1],tmp.val[2]+1,tmp.val[3]+1});
        residue[root[x]][1] = min({tmp.val[0]+1,tmp.val[1]+1,tmp.val[2],tmp.val[3]});
        ST.Update(1,1,n,pos[p],residue[root[x]][0],0);
        ST.Update(1,1,n,pos[p],residue[root[x]][1],1);
        x = p;
    }
    return ST.Get(1,1,n,tin[1],tout[1]);
}

int cat(signed x){
    ST.Update(1,1,n,pos[x],INF,1);
    Node tmp = CBT(x);

//    cout << tmp.mn() << endl;

    pre[x] = 1;

    return tmp.mn();
}

int dog(signed x){
    ST.Update(1,1,n,pos[x],INF,0);
    Node tmp = CBT(x);

//    cout << tmp.mn() << endl;

    pre[x] = 2;

    return tmp.mn();
}

signed neighbor(signed x){
    if (pre[x] == 1){
        ST.Update(1,1,n,pos[x],-INF,1);
    }
    if (pre[x] == 2){
        ST.Update(1,1,n,pos[x],-INF,0);
    }

    Node tmp = CBT(x);

//    cout << tmp.mn() << endl;

    pre[x] = 0;

    return tmp.mn();
}

void initialize(signed _n, vector<signed> u, vector<signed> v){
    n = _n;
    for (int i=0; i<n-1; i++){
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    DFS(1,0);
    HLD(1,1);
    ST.Build(n);
}

//int _n,q;
//int u[N],v[N];
//

//void Solve(){
//    cin >> _n;
//    for (int i=0; i<_n-1; i++){
//        cin >> u[i] >> v[i];
//    }
//    initialize(_n,u,v);
//
//    cin >> q;
//    while (q--){
//        int t,x;
//        cin >> t >> x;
//        if (t==1) cout << cat(x) << endl;
//        if (t==2) cout << dog(x) << endl;
//        if (t==3) cout << neighbor(x) << endl;
//    }
//
//}
//

//signed main(){
////    freopen("catsordogs.inp","r",stdin);
////    freopen("catsordogs.out","w",stdout);
////    ios_base::sync_with_stdio(0);
////    cin.tie(0);
//
//    Solve();
//
//    return 0;
//}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14160 KB Output is correct
2 Correct 7 ms 14208 KB Output is correct
3 Correct 7 ms 14160 KB Output is correct
4 Correct 7 ms 14160 KB Output is correct
5 Correct 7 ms 14160 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 7 ms 14160 KB Output is correct
8 Correct 7 ms 14160 KB Output is correct
9 Correct 7 ms 14356 KB Output is correct
10 Correct 7 ms 14160 KB Output is correct
11 Correct 7 ms 14264 KB Output is correct
12 Correct 7 ms 14160 KB Output is correct
13 Correct 7 ms 14160 KB Output is correct
14 Correct 7 ms 14160 KB Output is correct
15 Correct 7 ms 14252 KB Output is correct
16 Correct 7 ms 14188 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14160 KB Output is correct
2 Correct 7 ms 14208 KB Output is correct
3 Correct 7 ms 14160 KB Output is correct
4 Correct 7 ms 14160 KB Output is correct
5 Correct 7 ms 14160 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 7 ms 14160 KB Output is correct
8 Correct 7 ms 14160 KB Output is correct
9 Correct 7 ms 14356 KB Output is correct
10 Correct 7 ms 14160 KB Output is correct
11 Correct 7 ms 14264 KB Output is correct
12 Correct 7 ms 14160 KB Output is correct
13 Correct 7 ms 14160 KB Output is correct
14 Correct 7 ms 14160 KB Output is correct
15 Correct 7 ms 14252 KB Output is correct
16 Correct 7 ms 14188 KB Output is correct
17 Correct 15 ms 14416 KB Output is correct
18 Correct 20 ms 14672 KB Output is correct
19 Correct 12 ms 14620 KB Output is correct
20 Correct 7 ms 14416 KB Output is correct
21 Correct 9 ms 14428 KB Output is correct
22 Correct 9 ms 14416 KB Output is correct
23 Correct 23 ms 14416 KB Output is correct
24 Correct 15 ms 14416 KB Output is correct
25 Correct 12 ms 14528 KB Output is correct
26 Correct 9 ms 14416 KB Output is correct
27 Correct 8 ms 14416 KB Output is correct
28 Correct 9 ms 14672 KB Output is correct
29 Correct 10 ms 14672 KB Output is correct
30 Correct 10 ms 14416 KB Output is correct
31 Correct 8 ms 14416 KB Output is correct
32 Correct 10 ms 14584 KB Output is correct

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14160 KB Output is correct
2 Correct 7 ms 14208 KB Output is correct
3 Correct 7 ms 14160 KB Output is correct
4 Correct 7 ms 14160 KB Output is correct
5 Correct 7 ms 14160 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 7 ms 14160 KB Output is correct
8 Correct 7 ms 14160 KB Output is correct
9 Correct 7 ms 14356 KB Output is correct
10 Correct 7 ms 14160 KB Output is correct
11 Correct 7 ms 14264 KB Output is correct
12 Correct 7 ms 14160 KB Output is correct
13 Correct 7 ms 14160 KB Output is correct
14 Correct 7 ms 14160 KB Output is correct
15 Correct 7 ms 14252 KB Output is correct
16 Correct 7 ms 14188 KB Output is correct
17 Correct 15 ms 14416 KB Output is correct
18 Correct 20 ms 14672 KB Output is correct
19 Correct 12 ms 14620 KB Output is correct
20 Correct 7 ms 14416 KB Output is correct
21 Correct 9 ms 14428 KB Output is correct
22 Correct 9 ms 14416 KB Output is correct
23 Correct 23 ms 14416 KB Output is correct
24 Correct 15 ms 14416 KB Output is correct
25 Correct 12 ms 14528 KB Output is correct
26 Correct 9 ms 14416 KB Output is correct
27 Correct 8 ms 14416 KB Output is correct
28 Correct 9 ms 14672 KB Output is correct
29 Correct 10 ms 14672 KB Output is correct
30 Correct 10 ms 14416 KB Output is correct
31 Correct 8 ms 14416 KB Output is correct
32 Correct 10 ms 14584 KB Output is correct
33 Correct 2036 ms 33156 KB Output is correct
34 Correct 515 ms 36936 KB Output is correct
35 Correct 1805 ms 27512 KB Output is correct
36 Execution timed out 3066 ms 46152 KB Time limit exceeded
37 Halted 0 ms 0 KB -