Submission #65731

#	Time	Username	Problem	Language	Result	Execution time	Memory
65731		Benq	Cats or Dogs (JOI18_catdog)	C++11	100 / 100	2634 ms	73136 KiB

catdog

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
 
const int MOD = 1000000007;
const pi INF =  {-MOD,MOD};
const int MX = 100001;
 
// #define LOCAL 
 
#ifdef LOCAL 
#else
    #include "catdog.h"
#endif

// UTILITY

pi operator + (const pi& l, const pi& r) { 
    if (l == INF) return l;
    return {l.f+r.f,l.s+r.s}; 
}
pi operator += (pi& l, const pi& r) {  return l = l+r; }
pi operator + (const pi& l, const int& r) { return l+mp(r,r); }
pi operator += (pi& l, const int& r) { return l = l+r; }

pi operator - (const pi& l, const pi& r) { 
    if (l == INF) return l;
    return {l.f-r.f,l.s-r.s}; 
}

pi operator -= (pi& l, const pi& r) { return l = l-r; }

pi comb(pi x, pi y) { 
    if (x == mp(-MOD,MOD)) return x;
    return {min(x.f,y.f),max(x.s,y.s)}; 
}

pi neg(pi a) { return {-a.f,-a.s}; }

template<int SZ> struct L {
    typedef pi T;
    
    T dif[2*SZ], lazy[2*SZ]; // set SZ to a power of 2
    
    L() {
        memset (dif,0,sizeof dif);
        memset (lazy,0,sizeof lazy);
    }
    
    void ad(int ind, pi x) {
        lazy[ind] += x;
        dif[ind] += x.f-x.s;
    }
    
    void push(int ind, int L, int R) {
        if (L == R) return;
        if (L != R) {
            ad(2*ind,lazy[ind]);
            ad(2*ind+1,lazy[ind]);
        }
        lazy[ind] = {0,0};
    }
    
    void pull(int ind) { dif[ind] = comb(dif[2*ind],dif[2*ind+1]); }
    
    /*T query(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) { // get difference
        push(ind,L,R);
        if (lo > R || L > hi) return neg(INF);
        if (lo <= L && R <= hi) return dif[ind];
        
        int M = (L+R)/2;
        return comb(query(lo,hi,2*ind,L,M), query(lo,hi,2*ind+1,M+1,R));
    }*/
    
    T getLazy(int x, int ind = 1, int L = 0, int R = SZ-1) { // OK
        if (L == R) return lazy[ind];
        push(ind,L,R);
        int M = (L+R)/2;
        if (x <= M) return getLazy(x,2*ind,L,M);
        return getLazy(x,2*ind+1,M+1,R);
    }
    
    void upd(int lo, int hi, T inc, int ind = 1, int L = 0, int R = SZ-1) {
        push(ind,L,R);
        if (hi < L || R < lo) return;
        if (lo <= L && R <= hi) {
            ad(ind,inc);
            push(ind,L,R);
            return;
        }
        
        int M = (L+R)/2;
        upd(lo,hi,inc,2*ind,L,M); upd(lo,hi,inc,2*ind+1,M+1,R);
        pull(ind);
    }
    
    void adDif(int x, int z, int ind = 1, int L = 0, int R = SZ-1) { // TODO
        if (x < L || x > R) return;
        if (L == R) {
            if (z == -1) {
                dif[ind] = mp(0,0)+(lazy[ind].f-lazy[ind].s);
            } else {
                dif[ind] = INF;
            }
            return;
        }
        push(ind,L,R);
        int M = (L+R)/2;
        adDif(x,z,2*ind,L,M); adDif(x,z,2*ind+1,M+1,R);
        pull(ind);
    }
    
    int getFst(int x, pi t, int ind = 1, int L = 0, int R = SZ-1) { // TODO
        push(ind,L,R);
        int M = (L+R)/2;
        
        if (L == R) {
            if (comb(t,dif[ind]) == t) return L;
            return L+1;
        }
        
        if (x <= M) return getFst(x,t,2*ind,L,M);
        if (x <= R) {
            int tmp = getFst(x,t,2*ind+1,M+1,R);
            if (tmp != M+1) return tmp;
            return getFst(x,t,2*ind,L,M);
        }
        
        if (comb(t,dif[2*ind+1]) != t) return getFst(x,t,2*ind+1,M+1,R);
        return getFst(x,t,2*ind,L,M);
        /*
        int tmp = getFst(x,t,2*ind+1,M+1,R);
        if (tmp == M+1) return getFst(x,t,2*ind,L,M);
        return tmp;*/
    }
};

vector<vi> graph;

template <int V> struct HeavyLight { // sum queries, sum updates
    int parent[V], heavy[V], depth[V];
    int root[V], treePos[V], rTreePos[V];
    L<V> val, child;

    void init() {
        int n = sz(graph)-1;
        FOR(i,1,n+1) heavy[i] = -1;
        parent[1] = -1, depth[1] = 0;
        dfs(1);
        for (int i = 1, currentPos = 0; i <= n; ++i)
		if (parent[i] == -1 || heavy[parent[i]] != i)
			for (int j = i; j != -1; j = heavy[j]) {
				root[j] = i;
				treePos[j] = currentPos;
				rTreePos[currentPos] = j;
				currentPos ++;
			}
    }
    
    int dfs(int v) {
        int size = 1, maxSubtree = 0;
        for (auto u : graph[v]) if (u != parent[v]) {
            parent[u] = v;
            depth[u] = depth[v] + 1;
            int subtree = dfs(u);
            if (subtree > maxSubtree) heavy[v] = u, maxSubtree = subtree;
            size += subtree;
        }
        return size;
    }

    template <class BinaryOperation>
    void processPath(int u, int v, BinaryOperation op) {
        for (; root[u] != root[v]; v = parent[root[v]]) {
            if (depth[root[u]] > depth[root[v]]) swap(u, v);
            op(treePos[root[v]], treePos[v]);
        }
        if (depth[u] > depth[v]) swap(u, v);
        op(treePos[u], treePos[v]); // assumes values are stored in vertices
    }

    pi get(int x) { return val.getLazy(treePos[x]); }
    
    void upd(int x, int y, pi z) {
        if (y == 0) return;
        // cout << "OH " << x << " " << y << "\n";
        processPath(x,y,[this, &z](int l, int r) { val.upd(l,r,z); });
        if (y != 1) {
            //cout << "HI " << max(1,parent[x]) << " " << parent[y] << " " << z << "\n";
            processPath(max(1,parent[x]),parent[y],[this, &z](int l, int r) { child.upd(l,r,z); });
            //cout << child.getLazy(treePos[1]) << "\n";
        }
    }
    
    void adDif(int v, int x) { child.adDif(treePos[v],x); }
    
    int getFst(int v, pi x) { // TODO
        int lst = v; v = parent[v];
        while (v) {
            int t = child.getFst(treePos[v],x);
            if (t > treePos[root[v]]) {
                if (t == treePos[v]+1) return lst;
                // cout << "AH " << t << " " << rTreePos[t] << "\n";
                return rTreePos[t];
            }
            lst = root[v]; v = parent[lst];
        }
        return 1;
    }
};

HeavyLight<1<<17> H;

int N, st[MX];

pi trans(int v, pi x) {
    switch(v) {
        case 1: return {x.f,x.f+1};
        case 2: return {x.s+1,x.s};
        default:
            x.s = min(x.s,x.f+1);
            x.f = min(x.f,x.s+1);
            return x;
    }
}

int query() { 
    pi x = H.get(1); 
    return min(x.f,x.s);
}
 
void initialize(int n, std::vector<int> A, std::vector<int> B) {
    N = n;
    graph.resize(N+1);
    F0R(i,N-1) graph[A[i]].pb(B[i]), graph[B[i]].pb(A[i]);
    H.init();
}
 
pi eval(int v) { return trans(st[v],H.child.getLazy(H.treePos[v])); }

ostream& operator<<(ostream& o, const pi& x) {
    o << x.f << " " << x.s << " | ";
    return o;
}

void upd(int v, pi x) {
    int m = min(x.f,x.s);
    H.upd(1,v,{m,m});
    x.f -= m, x.s -= m;
    while (x.f || x.s) {
        int z;
        if (x.f) {
            z = H.getFst(v,{-1,0});
            H.upd(z,v,{1,0});
            x.f --;
        } else {
            z = H.getFst(v,{0,1});
            H.upd(z,v,{0,1});
            x.s --;
        }
        if (z > 1) {
            pi t = eval(H.parent[z])-H.get(H.parent[z]);
            if (t.f != t.s) {
                cout << "BAD " << z << " " << v << "\n" << st[H.parent[z]] << " " << eval(H.parent[z]) << "\n" << H.get(H.parent[z]) << "\n";
                exit(0);
            }
            H.upd(1,H.parent[z],t);
        }
    }
}

int change(int ind, int v) {
    if (st[v]) H.adDif(v,-1);
    st[v] = ind;
    if (st[v]) H.adDif(v,1);
    upd(v,eval(v)+neg(H.get(v)));
    
    pi x = H.get(1);
    if (x.f < 0 || x.s < 0) {
        // cout << H.get(2) << " " << " | " << H.get(1) << " " << "|" << " " << H.child.getLazy(1) << " " << eval(1) << "\n";
        exit(0);
    }
    return min(x.f,x.s);
}

int cat(int v) { return change(1,v); }
int dog(int v) { return change(2,v); }
int neighbor(int v) { return change(0,v); }
 
#ifdef LOCAL 
int readInt(){
	int i;
	if(scanf("%d",&i)!=1){
		fprintf(stderr,"Error while reading input\n");
		exit(1);
	}
	return i;
}
 
int main(){
	int N=readInt();
	
	std::vector<int> A(N-1),B(N-1);
	for(int i=0;i<N-1;i++)
	{
		A[i]=readInt();
		B[i]=readInt();
	}
	int Q;
	assert(scanf("%d",&Q)==1);
	std::vector <int> T(Q),V(Q);
	for(int i=0;i<Q;i++)
	{
		T[i]=readInt();
		V[i]=readInt();
	}
	
	initialize(N,A,B);
	
	std::vector<int> res(Q);
	for(int j=0;j<Q;j++)
	{
		if(T[j]==1) res[j]=cat(V[j]);
		else if(T[j]==2) res[j]=dog(V[j]);
		else res[j]=neighbor(V[j]);
		if (res[j] < 0) cout << "AH " << j << " " << T[j] << " " << V[j] << "\n";
	}
	for(int j=0;j<Q;j++)
		printf("%d\n",res[j]);
	return 0;
}
#endif

/*
0 
1 
1 
2 
1 
*/
 
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

• Subtask 1: 8 / 8
• Subtask 2: 30 / 30
• Subtask 3: 62 / 62