oj.uz

Submission #1001297

# Submission time Handle Problem Language Result Execution time Memory
1001297 2024-06-18T18:19:32 Z LonlyR Tourism (JOI23_tourism) C++17
10 / 100
 5000 ms 31568 KB 
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define ii pair<int,int>
#define ff first
#define ss second
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;
const int maxn = 1e5 + 5, bl = sqrt(maxn) ;
int n, m, q, cnt, cur;
int in[maxn], out[maxn], h[maxn], par[18][maxn], id[maxn], c[maxn], ans[maxn], in_set[maxn];
vector<int> adj[maxn], euler = {0};
int lgs[3*maxn];

int rev_in[maxn];

set<int> s;

inline int gilbertOrder(int x, int y, int pow, int rotate) {
	if (pow == 0) {
		return 0;
	}
	int hpow = 1 << (pow-1);
	int seg = (x < hpow) ? (
		(y < hpow) ? 0 : 3
	) : (
		(y < hpow) ? 1 : 2
	);
	seg = (seg + rotate) & 3;
	const int rotateDelta[4] = {3, 0, 0, 1};
	int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
	int nrot = (rotate + rotateDelta[seg]) & 3;
	int subSquareSize = int(1) << (2*pow - 2);
	int ans = seg * subSquareSize;
	int add = gilbertOrder(nx, ny, pow-1, nrot);
	ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
	return ans;
}

struct Q {
	int l, r, id;
	int ord;

	inline void calcOrder() {
		ord = gilbertOrder(l, r, 21, 0);
	}
} qr[maxn];

inline bool operator<(const Q &a, const Q &b) {
	return a.ord < b.ord;
}

void dfs(int x = 1, int p = 1)
{
    h[x] = h[p] + 1;
    in[x] = ++cnt;
    id[x] = euler.size();
    euler.push_back(x);
    for (int i : adj[x]) if (i != p)
        dfs(i, x),
        euler.push_back(x);
    out[x] = cnt;
}

//inline bool sub(int u, int v) /// u in subtree of v
//{
//    return in[v] <= in[u] && out[u] <= out[v];
//}
//
//int lca(int u, int v)
//{
//    if (h[u] > h[v]) swap(u, v);
//    if (sub(v, u)) return u;
//    for (int i = 17; i >= 0; i--)
//        if (sub(u, par[i][v]) == 0)
//            v = par[i][v];
//    return par[0][v];
//}

vector<vector<ii>> st;

inline void build()
{
    int sz = euler.size();
    int LG = __lg(sz);
    st = vector<vector<ii>>(LG + 1, vector<ii>(sz, {sz, 0}));
    for (int i = 1; i < sz; i++) st[0][i] = {h[euler[i]], euler[i]};
    for (int j = 1; j <= LG; j++)
        for (int i = 1; i + (1 << j) - 1 < sz; i++)
            st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}

inline int lca(int l, int r)
{
    l = id[l];
    r = id[r];
    if (l > r) swap(l, r);
//    assert(r-l+1<=n);
    int k = lgs[(r - l + 1)];
    return min(st[k][l], st[k][r - (1 << k) + 1]).ss;
}

inline void add(int x)
{
    x = c[x];
    in_set[x]++;
    if (in_set[x] == 1)
    {
        cur += h[x];
        if (s.size() == 0) return s.insert(in[x]), void();
        auto it = s.lower_bound(in[x]);
        if (it == s.begin())
            cur -= h[lca(x, rev_in[*it])];
        else if (it == s.end())
            cur -= h[lca(x, rev_in[*prev(it)])];
        else
        {
            auto u = rev_in[*it], v = rev_in[*prev(it)];
            cur += h[lca(u, v)];
            cur -= h[lca(u, x)];
            cur -= h[lca(v, x)];
        }
    }
    s.insert(in[x]);
}

inline void del(int x)
{
    x = c[x];
    in_set[x]--;
    if (in_set[x] == 0)
    {
        cur -= h[x];
        if (s.size() == 1) return s.clear(), void();
        auto it = s.lower_bound(in[x]);
        if (it == s.begin())
            cur += h[lca(x, rev_in[*next(it)])];
        else if (next(it) == s.end())
            cur += h[lca(x, rev_in[*prev(it)])];
        else
        {
            auto u = rev_in[*prev(it)], v = rev_in[*next(it)];
            cur -= h[lca(u, v)];
            cur += h[lca(u, x)];
            cur += h[lca(v, x)];
        }
        s.erase(it);
    }

}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); //cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> m >> q;
    for (int i = 1, u, v; i < n; i++)
        cin >> u >> v,
        adj[u].push_back(v),
        adj[v].push_back(u);
    for (int i = 1; i <= m; i++)
        cin >> c[i];
    dfs();
    for (int i = 1; i <= 3*n; i++) lgs[i] = __lg(i);
    build();
    for (int i = 1; i <= n; i++) rev_in[in[i]] = i;
    for (int i = 1; i <= q; i++)
        cin >> qr[i].l >> qr[i].r, qr[i].id = i, qr[i].calcOrder();
    sort(qr + 1, qr + q + 1);
    for (int i = 1, l = 1, r = 0; i <= q; i++)
    {
        auto [lx, rx, id, tmp] = qr[i];
        while (r < rx) add(++r);
        while (l > lx) add(--l);
        while (r > rx) del(r--);
        while (l < lx) del(l++);
        ans[id] = cur - h[lca(rev_in[*s.begin()], rev_in[*s.rbegin()])] + 1;
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8636 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8536 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 1 ms 8632 KB Output is correct
20 Correct 1 ms 8540 KB Output is correct
21 Correct 2 ms 8540 KB Output is correct
22 Correct 1 ms 8540 KB Output is correct
23 Correct 1 ms 8540 KB Output is correct
24 Correct 1 ms 8540 KB Output is correct
25 Correct 1 ms 8540 KB Output is correct
26 Correct 1 ms 8540 KB Output is correct
27 Correct 1 ms 8540 KB Output is correct
28 Correct 1 ms 8540 KB Output is correct
29 Correct 2 ms 8540 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8636 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8536 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 1 ms 8632 KB Output is correct
20 Correct 1 ms 8540 KB Output is correct
21 Correct 2 ms 8540 KB Output is correct
22 Correct 1 ms 8540 KB Output is correct
23 Correct 1 ms 8540 KB Output is correct
24 Correct 1 ms 8540 KB Output is correct
25 Correct 1 ms 8540 KB Output is correct
26 Correct 1 ms 8540 KB Output is correct
27 Correct 1 ms 8540 KB Output is correct
28 Correct 1 ms 8540 KB Output is correct
29 Correct 2 ms 8540 KB Output is correct
30 Correct 6 ms 9052 KB Output is correct
31 Correct 6 ms 9052 KB Output is correct
32 Correct 9 ms 9052 KB Output is correct
33 Correct 10 ms 9052 KB Output is correct
34 Correct 8 ms 9248 KB Output is correct
35 Correct 3 ms 9248 KB Output is correct
36 Correct 2 ms 9052 KB Output is correct
37 Correct 2 ms 9136 KB Output is correct
38 Correct 8 ms 9308 KB Output is correct
39 Correct 9 ms 9308 KB Output is correct
40 Correct 8 ms 9336 KB Output is correct
41 Correct 2 ms 9308 KB Output is correct
42 Correct 2 ms 9308 KB Output is correct
43 Correct 2 ms 9308 KB Output is correct
44 Correct 9 ms 9284 KB Output is correct
45 Correct 9 ms 9264 KB Output is correct
46 Correct 9 ms 9304 KB Output is correct
47 Correct 3 ms 9052 KB Output is correct
48 Correct 3 ms 9052 KB Output is correct
49 Correct 2 ms 9308 KB Output is correct
50 Correct 7 ms 9248 KB Output is correct
51 Correct 8 ms 9052 KB Output is correct
52 Correct 7 ms 9052 KB Output is correct
53 Correct 7 ms 9048 KB Output is correct
54 Correct 8 ms 9052 KB Output is correct
55 Correct 7 ms 9260 KB Output is correct
56 Correct 2 ms 8540 KB Output is correct
57 Correct 2 ms 9052 KB Output is correct
58 Correct 2 ms 9052 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Execution timed out 5095 ms 31568 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 114 ms 27612 KB Output is correct
3 Execution timed out 5051 ms 29220 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 2 ms 8724 KB Output is correct
4 Execution timed out 5100 ms 28452 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8636 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8536 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 1 ms 8632 KB Output is correct
20 Correct 1 ms 8540 KB Output is correct
21 Correct 2 ms 8540 KB Output is correct
22 Correct 1 ms 8540 KB Output is correct
23 Correct 1 ms 8540 KB Output is correct
24 Correct 1 ms 8540 KB Output is correct
25 Correct 1 ms 8540 KB Output is correct
26 Correct 1 ms 8540 KB Output is correct
27 Correct 1 ms 8540 KB Output is correct
28 Correct 1 ms 8540 KB Output is correct
29 Correct 2 ms 8540 KB Output is correct
30 Correct 6 ms 9052 KB Output is correct
31 Correct 6 ms 9052 KB Output is correct
32 Correct 9 ms 9052 KB Output is correct
33 Correct 10 ms 9052 KB Output is correct
34 Correct 8 ms 9248 KB Output is correct
35 Correct 3 ms 9248 KB Output is correct
36 Correct 2 ms 9052 KB Output is correct
37 Correct 2 ms 9136 KB Output is correct
38 Correct 8 ms 9308 KB Output is correct
39 Correct 9 ms 9308 KB Output is correct
40 Correct 8 ms 9336 KB Output is correct
41 Correct 2 ms 9308 KB Output is correct
42 Correct 2 ms 9308 KB Output is correct
43 Correct 2 ms 9308 KB Output is correct
44 Correct 9 ms 9284 KB Output is correct
45 Correct 9 ms 9264 KB Output is correct
46 Correct 9 ms 9304 KB Output is correct
47 Correct 3 ms 9052 KB Output is correct
48 Correct 3 ms 9052 KB Output is correct
49 Correct 2 ms 9308 KB Output is correct
50 Correct 7 ms 9248 KB Output is correct
51 Correct 8 ms 9052 KB Output is correct
52 Correct 7 ms 9052 KB Output is correct
53 Correct 7 ms 9048 KB Output is correct
54 Correct 8 ms 9052 KB Output is correct
55 Correct 7 ms 9260 KB Output is correct
56 Correct 2 ms 8540 KB Output is correct
57 Correct 2 ms 9052 KB Output is correct
58 Correct 2 ms 9052 KB Output is correct
59 Correct 1 ms 8540 KB Output is correct
60 Correct 1 ms 8536 KB Output is correct
61 Correct 2 ms 8540 KB Output is correct
62 Execution timed out 5095 ms 31568 KB Time limit exceeded
63 Halted 0 ms 0 KB -