답안 #65731 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65731	2018-08-08T14:52:02 Z	Benq	Cats or Dogs (JOI18_catdog)	C++11	100 / 100	2634 ms	73136 KB

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.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	8568 KB	Output is correct
2	Correct	12 ms	8684 KB	Output is correct
3	Correct	12 ms	8684 KB	Output is correct
4	Correct	12 ms	8684 KB	Output is correct
5	Correct	11 ms	8704 KB	Output is correct
6	Correct	11 ms	8752 KB	Output is correct
7	Correct	11 ms	8752 KB	Output is correct
8	Correct	10 ms	8788 KB	Output is correct
9	Correct	11 ms	8788 KB	Output is correct
10	Correct	11 ms	8816 KB	Output is correct
11	Correct	10 ms	8816 KB	Output is correct
12	Correct	9 ms	8816 KB	Output is correct
13	Correct	10 ms	8816 KB	Output is correct
14	Correct	10 ms	8816 KB	Output is correct
15	Correct	9 ms	8816 KB	Output is correct
16	Correct	9 ms	8816 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	8568 KB	Output is correct
2	Correct	12 ms	8684 KB	Output is correct
3	Correct	12 ms	8684 KB	Output is correct
4	Correct	12 ms	8684 KB	Output is correct
5	Correct	11 ms	8704 KB	Output is correct
6	Correct	11 ms	8752 KB	Output is correct
7	Correct	11 ms	8752 KB	Output is correct
8	Correct	10 ms	8788 KB	Output is correct
9	Correct	11 ms	8788 KB	Output is correct
10	Correct	11 ms	8816 KB	Output is correct
11	Correct	10 ms	8816 KB	Output is correct
12	Correct	9 ms	8816 KB	Output is correct
13	Correct	10 ms	8816 KB	Output is correct
14	Correct	10 ms	8816 KB	Output is correct
15	Correct	9 ms	8816 KB	Output is correct
16	Correct	9 ms	8816 KB	Output is correct
17	Correct	22 ms	8816 KB	Output is correct
18	Correct	17 ms	8940 KB	Output is correct
19	Correct	14 ms	8940 KB	Output is correct
20	Correct	9 ms	8940 KB	Output is correct
21	Correct	14 ms	8940 KB	Output is correct
22	Correct	15 ms	8940 KB	Output is correct
23	Correct	23 ms	8996 KB	Output is correct
24	Correct	23 ms	8996 KB	Output is correct
25	Correct	18 ms	8996 KB	Output is correct
26	Correct	12 ms	8996 KB	Output is correct
27	Correct	12 ms	8996 KB	Output is correct
28	Correct	12 ms	8996 KB	Output is correct
29	Correct	18 ms	8996 KB	Output is correct
30	Correct	13 ms	8996 KB	Output is correct
31	Correct	11 ms	8996 KB	Output is correct
32	Correct	14 ms	8996 KB	Output is correct

Subtask #3
62.0 / 62.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	8568 KB	Output is correct
2	Correct	12 ms	8684 KB	Output is correct
3	Correct	12 ms	8684 KB	Output is correct
4	Correct	12 ms	8684 KB	Output is correct
5	Correct	11 ms	8704 KB	Output is correct
6	Correct	11 ms	8752 KB	Output is correct
7	Correct	11 ms	8752 KB	Output is correct
8	Correct	10 ms	8788 KB	Output is correct
9	Correct	11 ms	8788 KB	Output is correct
10	Correct	11 ms	8816 KB	Output is correct
11	Correct	10 ms	8816 KB	Output is correct
12	Correct	9 ms	8816 KB	Output is correct
13	Correct	10 ms	8816 KB	Output is correct
14	Correct	10 ms	8816 KB	Output is correct
15	Correct	9 ms	8816 KB	Output is correct
16	Correct	9 ms	8816 KB	Output is correct
17	Correct	22 ms	8816 KB	Output is correct
18	Correct	17 ms	8940 KB	Output is correct
19	Correct	14 ms	8940 KB	Output is correct
20	Correct	9 ms	8940 KB	Output is correct
21	Correct	14 ms	8940 KB	Output is correct
22	Correct	15 ms	8940 KB	Output is correct
23	Correct	23 ms	8996 KB	Output is correct
24	Correct	23 ms	8996 KB	Output is correct
25	Correct	18 ms	8996 KB	Output is correct
26	Correct	12 ms	8996 KB	Output is correct
27	Correct	12 ms	8996 KB	Output is correct
28	Correct	12 ms	8996 KB	Output is correct
29	Correct	18 ms	8996 KB	Output is correct
30	Correct	13 ms	8996 KB	Output is correct
31	Correct	11 ms	8996 KB	Output is correct
32	Correct	14 ms	8996 KB	Output is correct
33	Correct	1491 ms	14632 KB	Output is correct
34	Correct	475 ms	15120 KB	Output is correct
35	Correct	1471 ms	15120 KB	Output is correct
36	Correct	2225 ms	18620 KB	Output is correct
37	Correct	32 ms	18620 KB	Output is correct
38	Correct	2634 ms	19668 KB	Output is correct
39	Correct	2471 ms	21660 KB	Output is correct
40	Correct	2138 ms	23488 KB	Output is correct
41	Correct	2412 ms	25540 KB	Output is correct
42	Correct	2336 ms	27548 KB	Output is correct
43	Correct	2445 ms	29444 KB	Output is correct
44	Correct	2410 ms	31336 KB	Output is correct
45	Correct	2223 ms	33240 KB	Output is correct
46	Correct	2469 ms	35288 KB	Output is correct
47	Correct	2283 ms	37072 KB	Output is correct
48	Correct	653 ms	37072 KB	Output is correct
49	Correct	630 ms	38944 KB	Output is correct
50	Correct	316 ms	38944 KB	Output is correct
51	Correct	309 ms	38944 KB	Output is correct
52	Correct	143 ms	38944 KB	Output is correct
53	Correct	930 ms	41636 KB	Output is correct
54	Correct	736 ms	41636 KB	Output is correct
55	Correct	2076 ms	41912 KB	Output is correct
56	Correct	1312 ms	41912 KB	Output is correct
57	Correct	1850 ms	46108 KB	Output is correct
58	Correct	73 ms	46108 KB	Output is correct
59	Correct	248 ms	46108 KB	Output is correct
60	Correct	510 ms	48252 KB	Output is correct
61	Correct	648 ms	50280 KB	Output is correct
62	Correct	319 ms	50280 KB	Output is correct
63	Correct	223 ms	50280 KB	Output is correct
64	Correct	201 ms	51672 KB	Output is correct
65	Correct	200 ms	57632 KB	Output is correct
66	Correct	642 ms	57632 KB	Output is correct
67	Correct	302 ms	57632 KB	Output is correct
68	Correct	842 ms	61204 KB	Output is correct
69	Correct	276 ms	61204 KB	Output is correct
70	Correct	83 ms	61204 KB	Output is correct
71	Correct	411 ms	61204 KB	Output is correct
72	Correct	447 ms	61240 KB	Output is correct
73	Correct	1395 ms	67228 KB	Output is correct
74	Correct	1410 ms	67228 KB	Output is correct
75	Correct	709 ms	71092 KB	Output is correct
76	Correct	684 ms	72364 KB	Output is correct
77	Correct	1240 ms	73136 KB	Output is correct

답안 #65731

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 30.0 / 30.0

Subtask #3 62.0 / 62.0

Subtask #1
8.0 / 8.0

Subtask #2
30.0 / 30.0

Subtask #3
62.0 / 62.0