oj.uz

Submission #1038694

# Submission time Handle Problem Language Result Execution time Memory
1038694 2024-07-30T06:21:08 Z 정민찬(#10987) JOI tour (JOI24_joitour) C++17
6 / 100
 797 ms 120964 KB 
#include "joitour.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

const ll B = 350;

struct Fenwick {
    vector<ll> tree;
    void init(ll n) {
        tree.resize(n+1);
    }
    void update(ll i, ll v, ll n) {
        while (i <= n) {
            tree[i] += v;
            i += i & -i;
        }
    }
    ll qry(ll i) {
        ll ret = 0;
        while (i) {	
            ret += tree[i];
            i -= i & -i;
        }
        return ret;
    }
    ll qry(ll l, ll r) {
        return qry(r) - qry(l-1);
    }
};

struct LazySegmentTree{
	vector<ll> tree;
	vector<ll> tree2;
	vector<ll> cnt;
	vector<ll> lazy;
	void init(ll n) {
		ll sz = 1 << __lg(n-1) + 2;
		tree.assign(sz, 0);
		tree2.assign(sz, 0);
		cnt.assign(sz, 0);
		lazy.assign(sz, 0);
	}
	void propagate(ll node, ll s, ll e) {
		tree[node] += lazy[node] * cnt[node];
		tree2[node] += lazy[node] * (e-s+1);
		if (s != e) {
			lazy[node*2] += lazy[node];
			lazy[node*2+1] += lazy[node];
		}
		lazy[node] = 0;
	}
	void update(ll node, ll s, ll e, ll l, ll r, ll v) {
		propagate(node, s, e);
		if (l > e || s > r) return;
		if (l <= s && e <= r) {
			lazy[node] = v;
			propagate(node, s, e);
			return;
		}
		ll mid = s + e >> 1;
		update(node*2, s, mid, l, r, v);
		update(node*2+1, mid+1, e, l, r, v);
		tree[node] = tree[node*2] + tree[node*2+1];
		cnt[node] = cnt[node*2] + cnt[node*2+1];
	}
	void modify(ll node, ll s, ll e, ll tar, ll state) {
		propagate(node, s, e);
		if (s > tar || tar > e) return;
		if (s == e) {
			cnt[node] = state;
			if (state == 1) tree[node] = tree2[node];
			else tree[node] = 0;
			return;
		}
		ll mid = s + e >> 1;
		modify(node*2, s, mid, tar, state);
		modify(node*2+1, mid+1, e, tar, state);
		tree[node] = tree[node*2] + tree[node*2+1];
		cnt[node] = cnt[node*2] + cnt[node*2+1];
	}
	ll query(ll node, ll s, ll e, ll l, ll r) {
		propagate(node, s, e);
		if (l > e || s > r) return 0;
		if (l <= s && e <= r) return tree[node];
		ll mid = s + e >> 1;
		return query(node*2, s, mid, l, r) + query(node*2+1, mid+1, e, l, r);
	}
};

ll n;
vector<ll> adj[200010];
vector<ll> g[200010];
ll T[3];
ll in[200010], out[200010];
ll pv;
ll sz[200010], par[200010];
ll dep[200010];

void dfs(ll x, ll p) {
    sz[x] = 1;
    for (auto &y : adj[x]) {
        if (y == p) continue;
        g[x].push_back(y);
        dep[y] = dep[x] + 1;
        par[y] = x;
        dfs(y, x);
        sz[x] += sz[y];
        if (sz[g[x][0]] < sz[y]) {
            swap(g[x][0], g[x].back());
        }
    }
}

ll tp[200010];

void dfs2(ll x) {
    in[x] = ++ pv;
    for (auto &y : g[x]) {
        tp[y] = y == g[x][0] ? tp[x] : y;
        dfs2(y);
    }
    out[x] = pv;
}

Fenwick seg0, seg1, seg2;
LazySegmentTree sub0, sub2;
LazySegmentTree psub0, psub2;
//LazySegmentTree sub20, sub02;

ll ans = 0;
ll F[200010];
ll TS[3];
vector<ll> lot;
ll sum[200010];

void init(int _N, vector<int> _F, vector<int> U, vector<int> V, int Q) {
	n = _N;
	for (ll i=1; i<=n; i++) {
		F[i] = _F[i-1];
	}
	for (ll i=1; i<=n; i++) {
        T[F[i]] ++;
    }
	for (ll i=0; i<n-1; i++) {
		adj[U[i]+1].push_back(V[i] + 1);
		adj[V[i]+1].push_back(U[i] + 1);
	}
	dep[1] = 1;
	dfs(1, 0);
	tp[1] = 1;
	dfs2(1);
	seg0.init(n); seg1.init(n); seg2.init(n);
	sub0.init(n); sub2.init(n);
	psub0.init(n); psub2.init(n);
	//sub02.init(n); sub20.init(n);
	for (ll i=1; i<=n; i++) {
        if (F[i] == 0) {
            seg0.update(in[i], 1, n);
        }
        else if (F[i] == 2) {
            seg2.update(in[i], 1, n);
        }
        else {
        	seg1.update(in[i], 1, n);
        }
    }
    for (ll i=1; i<=n; i++) {
    	ll ret0 = seg0.qry(in[i], out[i]);
        ll ret2 = seg2.qry(in[i], out[i]);
        if (F[i] == 1) {
        	sub0.modify(1, 1, n, in[i], 1);
        	sub2.modify(1, 1, n, in[i], 1);
        	ans += (T[0] - ret0) * (T[2] - ret2);
        	TS[0] += ret0;
        	TS[2] += ret2;
        }
        if (F[i] == 0) {
        	//TS[0] += dep[i];
        	//sub02.modify(1, 1, n, in[i], 1);
        }
        if (F[i] == 2) {
        	//TS[2] += dep[i];
        	//sub20.modify(1, 1, n, in[i], 1);
        }
        if (i != 1 && F[par[i]] == 1) {
        	psub0.modify(1, 1, n, in[i], 1);
        	psub2.modify(1, 1, n, in[i], 1);
        	ans += ret0 * ret2;
        }
        sub0.update(1, 1, n, in[i], in[i], ret0);
        sub2.update(1, 1, n, in[i], in[i], ret2);
        //sub02.update(1, 1, n, in[i], in[i], ret2);
        //sub20.update(1, 1, n, in[i], in[i], ret0);
        psub0.update(1, 1, n, in[i], in[i], ret0);
        psub2.update(1, 1, n, in[i], in[i], ret2);
    }
    for (ll i=1; i<=n; i++) {
    	if (g[i].size() > B) {
    		for (auto &j : g[i]) {
    			sum[i] += seg0.qry(in[j], out[j]) * seg2.qry(in[j], out[j]);
    		}
    		lot.push_back(i);
    	}
    }
}

ll Qquery1(ll x, ll t) {
	ll ret = 0;
	while (x) {
		if (t == 0)
			ret += sub0.query(1, 1, n, in[tp[x]], in[x]);
		else
			ret += sub2.query(1, 1, n, in[tp[x]], in[x]);
		x = par[tp[x]];
	}
	return ret;
}

ll Qquery2(ll x, ll t) {
	ll ret = 0;
	while (x) {
		if (tp[x] != 1 && F[par[tp[x]]] == 1) {
			if (t == 0)
				psub0.modify(1, 1, n, in[tp[x]], 1);
			else
				psub2.modify(1, 1, n, in[tp[x]], 1);
		}
		else {
			if (t == 0)
				psub0.modify(1, 1, n, in[tp[x]], 0);
			else
				psub2.modify(1, 1, n, in[tp[x]], 0);
		}
		if (t == 0)
			ret += psub0.query(1, 1, n, in[tp[x]], in[x]);
		else
			ret += psub2.query(1, 1, n, in[tp[x]], in[x]);
		x = par[tp[x]];
	}
	return ret;
}

ll Qquery3(ll x) {
	ll ret = 0;
	while (x) {
		ret += seg1.qry(in[tp[x]], in[x]);
		x = par[tp[x]];
	}
	return ret;
}

void Uupdate0(ll x, ll v) {
	while (x) {
		sub0.update(1, 1, n, in[tp[x]], in[x], v);
		psub0.update(1, 1, n, in[tp[x]], in[x], v);
		x = par[tp[x]];
	}
}

void Uupdate2(ll x, ll v) {
	while (x) {
		sub2.update(1, 1, n, in[tp[x]], in[x], v);
		psub2.update(1, 1, n, in[tp[x]], in[x], v);
		x = par[tp[x]];
	}
}

void change(int X, int v) {
	X ++;
	if (F[X] == 1) {
		if (g[X].size() > B) ans -= sum[X];
		else {
			for (auto &y : g[X]) {
				ans -= seg0.qry(in[y], out[y]) * seg2.qry(in[y], out[y]);
			}
		}
		ans -= (T[0] - seg0.qry(in[X], out[X])) * (T[2] - seg2.qry(in[X], out[X]));
		if (!g[X].empty()) {
			psub0.modify(1, 1, n, in[g[X][0]], 0);
			psub2.modify(1, 1, n, in[g[X][0]], 0);
		}
		sub0.modify(1, 1, n, in[X], 0);
		sub2.modify(1, 1, n, in[X], 0);
		T[1] --;
		seg1.update(in[X], -1, n);
		TS[0] -= seg0.qry(in[X], out[X]);
		TS[2] -= seg2.qry(in[X], out[X]);
	}
	else if (F[X] == 2) {
		Uupdate2(X, -1);
		TS[2] -= Qquery3(X);
		T[2] --;
		ans += TS[0] - Qquery1(X, 0);
		ans -= T[0] * (T[1] - Qquery3(X));
		ans -= Qquery2(X, 0);
		for (auto &y : lot) {
			if (y != X && in[y] <= in[X] && in[X] <= out[y]) {
				ll idx = upper_bound(g[y].begin(), g[y].end(), X, [&] (ll uu, ll vv) {
					return in[uu] < in[vv];
				}) - g[y].begin() - 1;
				ll ch = g[y][idx];
				sum[y] -= seg0.qry(in[ch], out[ch]);
			}
		}
		seg2.update(in[X], -1, n);
	}
	else if (F[X] == 0) {
		Uupdate0(X, -1);
		TS[0] -= Qquery3(X);
		T[0] --;
		ans += TS[2] - Qquery1(X, 2);
		ans -= T[2] * (T[1] - Qquery3(X));
		ans -= Qquery2(X, 2);
		for (auto &y : lot) {
			if (y != X && in[y] <= in[X] && in[X] <= out[y]) {
				ll idx = upper_bound(g[y].begin(), g[y].end(), X, [&] (ll uu, ll vv) {
					return in[uu] < in[vv];
				}) - g[y].begin() - 1;
				ll ch = g[y][idx];
				sum[y] -= seg2.qry(in[ch], out[ch]);
			}
		}
		seg0.update(in[X], -1, n);
	}

	F[X] = v;

	if (F[X] == 1) {
		if (g[X].size() > B) ans += sum[X];
		else {
			for (auto &y : g[X]) {
				ans += seg0.qry(in[y], out[y]) * seg2.qry(in[y], out[y]);
			}
		}
		ans += (T[0] - seg0.qry(in[X], out[X])) * (T[2] - seg2.qry(in[X], out[X]));
		if (!g[X].empty()) {
			psub0.modify(1, 1, n, in[g[X][0]], 1);
			psub2.modify(1, 1, n, in[g[X][0]], 1);
		}
		sub0.modify(1, 1, n, in[X], 1);
		sub2.modify(1, 1, n, in[X], 1);
		T[1] ++;
		seg1.update(in[X], 1, n);
		TS[0] += seg0.qry(in[X], out[X]);
		TS[2] += seg2.qry(in[X], out[X]);
	}
	else if (F[X] == 2) {
		Uupdate2(X, 1);
		TS[2] += Qquery3(X);
		T[2] ++;
		ans -= TS[0] - Qquery1(X, 0);
		ans += T[0] * (T[1] - Qquery3(X));
		ans += Qquery2(X, 0);
		for (auto &y : lot) {
			if (y != X && in[y] <= in[X] && in[X] <= out[y]) {
				ll idx = upper_bound(g[y].begin(), g[y].end(), X, [&] (ll uu, ll vv) {
					return in[uu] < in[vv];
				}) - g[y].begin() - 1;
				ll ch = g[y][idx];
				sum[y] += seg0.qry(in[ch], out[ch]);
			}
		}
		seg2.update(in[X], 1, n);
	}
	else if (F[X] == 0) {
		Uupdate0(X, 1);
		TS[0] += Qquery3(X);
		T[0] ++;
		ans -= TS[2] - Qquery1(X, 2);
		ans += T[2] * (T[1] - Qquery3(X));
		ans += Qquery2(X, 2);
		for (auto &y : lot) {
			if (y != X && in[y] <= in[X] && in[X] <= out[y]) {
				ll idx = upper_bound(g[y].begin(), g[y].end(), X, [&] (ll uu, ll vv) {
					return in[uu] < in[vv];
				}) - g[y].begin() - 1;
				ll ch = g[y][idx];
				sum[y] += seg2.qry(in[ch], out[ch]);
			}
		}
		seg0.update(in[X], -1, n);
	}
}

long long num_tours() {
	return T[0] * T[1] * T[2] - ans;
}

Compilation message

joitour.cpp: In member function 'void LazySegmentTree::init(ll)':
joitour.cpp:41:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   41 |   ll sz = 1 << __lg(n-1) + 2;
      |                ~~~~~~~~~~^~~
joitour.cpp: In member function 'void LazySegmentTree::update(ll, ll, ll, ll, ll, ll)':
joitour.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |   ll mid = s + e >> 1;
      |            ~~^~~
joitour.cpp: In member function 'void LazySegmentTree::modify(ll, ll, ll, ll, ll)':
joitour.cpp:79:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |   ll mid = s + e >> 1;
      |            ~~^~~
joitour.cpp: In member function 'll LazySegmentTree::query(ll, ll, ll, ll, ll)':
joitour.cpp:89:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |   ll mid = s + e >> 1;
      |            ~~^~~

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9816 KB Output is correct
3 Correct 4 ms 9816 KB Output is correct
4 Incorrect 5 ms 10072 KB Wrong Answer [1]
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9816 KB Output is correct
3 Correct 4 ms 9816 KB Output is correct
4 Incorrect 5 ms 10072 KB Wrong Answer [1]
5 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 715 ms 115892 KB Output is correct
3 Correct 745 ms 115596 KB Output is correct
4 Correct 648 ms 113312 KB Output is correct
5 Correct 797 ms 116388 KB Output is correct
6 Correct 373 ms 106832 KB Output is correct
7 Correct 407 ms 106912 KB Output is correct
8 Correct 670 ms 106564 KB Output is correct
9 Correct 710 ms 106836 KB Output is correct
10 Correct 648 ms 106832 KB Output is correct
11 Correct 734 ms 107600 KB Output is correct
12 Correct 640 ms 110420 KB Output is correct
13 Correct 767 ms 110672 KB Output is correct
14 Correct 602 ms 110416 KB Output is correct
15 Correct 772 ms 109904 KB Output is correct
16 Correct 721 ms 118288 KB Output is correct
17 Correct 4 ms 9816 KB Output is correct
18 Correct 3 ms 9816 KB Output is correct
19 Correct 4 ms 9816 KB Output is correct
20 Correct 4 ms 9816 KB Output is correct
21 Correct 682 ms 107348 KB Output is correct
22 Correct 765 ms 107404 KB Output is correct
23 Correct 647 ms 107428 KB Output is correct
24 Correct 790 ms 107420 KB Output is correct
25 Correct 626 ms 105276 KB Output is correct
26 Correct 616 ms 105448 KB Output is correct
27 Correct 533 ms 105344 KB Output is correct
28 Correct 716 ms 105276 KB Output is correct
29 Correct 404 ms 120736 KB Output is correct
30 Correct 436 ms 120912 KB Output is correct
31 Correct 357 ms 120964 KB Output is correct
32 Correct 455 ms 120912 KB Output is correct
33 Correct 467 ms 106668 KB Output is correct
34 Correct 476 ms 106872 KB Output is correct
35 Correct 397 ms 107088 KB Output is correct
36 Correct 455 ms 106832 KB Output is correct

Subtask #4
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9816 KB Output is correct
3 Incorrect 4 ms 9816 KB Wrong Answer [1]
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9812 KB Output is correct
2 Incorrect 5 ms 9816 KB Wrong Answer [1]
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9816 KB Output is correct
3 Correct 4 ms 9816 KB Output is correct
4 Incorrect 5 ms 10072 KB Wrong Answer [1]
5 Halted 0 ms 0 KB -

Subtask #7
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9816 KB Output is correct
3 Correct 4 ms 9816 KB Output is correct
4 Incorrect 5 ms 10072 KB Wrong Answer [1]
5 Halted 0 ms 0 KB -