oj.uz

Submission #1001180

# Submission time Handle Problem Language Result Execution time Memory
1001180 2024-06-18T16:37:12 Z LonlyR Tourism (JOI23_tourism) C++17
28 / 100
 5000 ms 31824 KB 
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(), x.end()

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];
vector<int> adj[maxn];

struct cmp
{
    bool operator() (int x, int y) const
    {
        return in[x] < in[y];
    }
};

multiset<int, cmp> s;

struct Q{
    int l, r, id;
    bool operator < (Q b) const
    {
        if (l / bl != b.l / bl) return l < b.l;
        return (l / bl & 1) ? (r < b.r) : (r > b.r);
    }
} qr[maxn];

void dfs(int x = 1, int p = 1)
{
    par[0][x] = p;
    h[x] = h[p] + 1;
    for (int i = 1; i < 18; i++)
        par[i][x] = par[i - 1][par[i - 1][x]];
    in[x] = ++cnt;
    for (int i : adj[x]) if (i != p)
        dfs(i, 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];
}

int dist(int u, int v, int w = -1)
{
    if (w == -1) return h[u] + h[v] - h[lca(u, v)] * 2;
    return h[u] + h[v] - h[w] * 2;
}

void add(int x)
{
    x = c[x];
    if (!s.count(x))
    {
        cur += h[x];
        if (s.size() == 0) return s.emplace(x), void();
        auto it = s.lower_bound(x);
        if (it == s.begin())
            cur -= h[lca(x, *it)];
        else if (it == s.end())
            cur -= h[lca(x, *prev(it))];
        else
        {
            auto u = *it, v = *prev(it);
            cur += h[lca(u, v)];
            cur -= h[lca(u, x)];
            cur -= h[lca(v, x)];
        }
    }
    return s.emplace(x), void();
}

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

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); 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].emplace_back(v),
        adj[v].emplace_back(u);
    for (int i = 1; i <= m; i++)
        cin >> c[i], id[i] = (i - 1) / bl + 1;
    dfs();
    for (int i = 1; i <= q; i++)
        cin >> qr[i].l >> qr[i].r, qr[i].id = i;
    sort(qr + 1, qr + q + 1);
    for (int i = 1, l = 1, r = 0; i <= q; i++)
    {
        auto [lx, rx, id] = 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(*s.begin(), *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 2 ms 16732 KB Output is correct
2 Correct 2 ms 16876 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 4 ms 12636 KB Output is correct
5 Correct 4 ms 16732 KB Output is correct
6 Correct 4 ms 16856 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 4 ms 16856 KB Output is correct
9 Correct 7 ms 16732 KB Output is correct
10 Correct 6 ms 16728 KB Output is correct
11 Correct 7 ms 16732 KB Output is correct
12 Correct 2 ms 16896 KB Output is correct
13 Correct 2 ms 16732 KB Output is correct
14 Correct 2 ms 16732 KB Output is correct
15 Correct 5 ms 16732 KB Output is correct
16 Correct 5 ms 16732 KB Output is correct
17 Correct 4 ms 16860 KB Output is correct
18 Correct 5 ms 16892 KB Output is correct
19 Correct 5 ms 16732 KB Output is correct
20 Correct 5 ms 16732 KB Output is correct
21 Correct 8 ms 16732 KB Output is correct
22 Correct 7 ms 16732 KB Output is correct
23 Correct 7 ms 16904 KB Output is correct
24 Correct 7 ms 16732 KB Output is correct
25 Correct 7 ms 16732 KB Output is correct
26 Correct 6 ms 16732 KB Output is correct
27 Correct 3 ms 16732 KB Output is correct
28 Correct 2 ms 16728 KB Output is correct
29 Correct 2 ms 16732 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 2 ms 16876 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 4 ms 12636 KB Output is correct
5 Correct 4 ms 16732 KB Output is correct
6 Correct 4 ms 16856 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 4 ms 16856 KB Output is correct
9 Correct 7 ms 16732 KB Output is correct
10 Correct 6 ms 16728 KB Output is correct
11 Correct 7 ms 16732 KB Output is correct
12 Correct 2 ms 16896 KB Output is correct
13 Correct 2 ms 16732 KB Output is correct
14 Correct 2 ms 16732 KB Output is correct
15 Correct 5 ms 16732 KB Output is correct
16 Correct 5 ms 16732 KB Output is correct
17 Correct 4 ms 16860 KB Output is correct
18 Correct 5 ms 16892 KB Output is correct
19 Correct 5 ms 16732 KB Output is correct
20 Correct 5 ms 16732 KB Output is correct
21 Correct 8 ms 16732 KB Output is correct
22 Correct 7 ms 16732 KB Output is correct
23 Correct 7 ms 16904 KB Output is correct
24 Correct 7 ms 16732 KB Output is correct
25 Correct 7 ms 16732 KB Output is correct
26 Correct 6 ms 16732 KB Output is correct
27 Correct 3 ms 16732 KB Output is correct
28 Correct 2 ms 16728 KB Output is correct
29 Correct 2 ms 16732 KB Output is correct
30 Correct 37 ms 16988 KB Output is correct
31 Correct 45 ms 16988 KB Output is correct
32 Correct 58 ms 17244 KB Output is correct
33 Correct 60 ms 17240 KB Output is correct
34 Correct 57 ms 17220 KB Output is correct
35 Correct 6 ms 17244 KB Output is correct
36 Correct 6 ms 17224 KB Output is correct
37 Correct 9 ms 17272 KB Output is correct
38 Correct 30 ms 17316 KB Output is correct
39 Correct 37 ms 17208 KB Output is correct
40 Correct 29 ms 17240 KB Output is correct
41 Correct 5 ms 17244 KB Output is correct
42 Correct 5 ms 17244 KB Output is correct
43 Correct 5 ms 17244 KB Output is correct
44 Correct 33 ms 17244 KB Output is correct
45 Correct 33 ms 17240 KB Output is correct
46 Correct 34 ms 17244 KB Output is correct
47 Correct 5 ms 17244 KB Output is correct
48 Correct 5 ms 17240 KB Output is correct
49 Correct 5 ms 17280 KB Output is correct
50 Correct 59 ms 17244 KB Output is correct
51 Correct 62 ms 17240 KB Output is correct
52 Correct 63 ms 17240 KB Output is correct
53 Correct 57 ms 17244 KB Output is correct
54 Correct 60 ms 17240 KB Output is correct
55 Correct 58 ms 17252 KB Output is correct
56 Correct 16 ms 16984 KB Output is correct
57 Correct 3 ms 16988 KB Output is correct
58 Correct 6 ms 17124 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 17 ms 16968 KB Output is correct
4 Execution timed out 5091 ms 31496 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 120 ms 22512 KB Output is correct
3 Correct 186 ms 23132 KB Output is correct
4 Correct 158 ms 23888 KB Output is correct
5 Correct 112 ms 31824 KB Output is correct
6 Correct 162 ms 30312 KB Output is correct
7 Correct 176 ms 27916 KB Output is correct
8 Correct 187 ms 27480 KB Output is correct
9 Correct 185 ms 27220 KB Output is correct
10 Correct 166 ms 27220 KB Output is correct
11 Correct 237 ms 26996 KB Output is correct
12 Correct 227 ms 27216 KB Output is correct
13 Correct 209 ms 27468 KB Output is correct
14 Correct 197 ms 28240 KB Output is correct
15 Correct 183 ms 30544 KB Output is correct
16 Correct 209 ms 29524 KB Output is correct
17 Correct 198 ms 29604 KB Output is correct
18 Correct 208 ms 29520 KB Output is correct
19 Correct 87 ms 31312 KB Output is correct
20 Correct 111 ms 31364 KB Output is correct
21 Correct 118 ms 28468 KB Output is correct
22 Correct 128 ms 27472 KB Output is correct
23 Correct 137 ms 26908 KB Output is correct
24 Correct 165 ms 26848 KB Output is correct
25 Correct 175 ms 26708 KB Output is correct
26 Correct 202 ms 26684 KB Output is correct
27 Correct 281 ms 26716 KB Output is correct
28 Correct 307 ms 26708 KB Output is correct
29 Correct 325 ms 26704 KB Output is correct
30 Correct 339 ms 26864 KB Output is correct
31 Correct 294 ms 27028 KB Output is correct
32 Correct 273 ms 27332 KB Output is correct
33 Correct 254 ms 28524 KB Output is correct
34 Correct 231 ms 30292 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 16 ms 16988 KB Output is correct
4 Execution timed out 5044 ms 30244 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 2 ms 16876 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 4 ms 12636 KB Output is correct
5 Correct 4 ms 16732 KB Output is correct
6 Correct 4 ms 16856 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 4 ms 16856 KB Output is correct
9 Correct 7 ms 16732 KB Output is correct
10 Correct 6 ms 16728 KB Output is correct
11 Correct 7 ms 16732 KB Output is correct
12 Correct 2 ms 16896 KB Output is correct
13 Correct 2 ms 16732 KB Output is correct
14 Correct 2 ms 16732 KB Output is correct
15 Correct 5 ms 16732 KB Output is correct
16 Correct 5 ms 16732 KB Output is correct
17 Correct 4 ms 16860 KB Output is correct
18 Correct 5 ms 16892 KB Output is correct
19 Correct 5 ms 16732 KB Output is correct
20 Correct 5 ms 16732 KB Output is correct
21 Correct 8 ms 16732 KB Output is correct
22 Correct 7 ms 16732 KB Output is correct
23 Correct 7 ms 16904 KB Output is correct
24 Correct 7 ms 16732 KB Output is correct
25 Correct 7 ms 16732 KB Output is correct
26 Correct 6 ms 16732 KB Output is correct
27 Correct 3 ms 16732 KB Output is correct
28 Correct 2 ms 16728 KB Output is correct
29 Correct 2 ms 16732 KB Output is correct
30 Correct 37 ms 16988 KB Output is correct
31 Correct 45 ms 16988 KB Output is correct
32 Correct 58 ms 17244 KB Output is correct
33 Correct 60 ms 17240 KB Output is correct
34 Correct 57 ms 17220 KB Output is correct
35 Correct 6 ms 17244 KB Output is correct
36 Correct 6 ms 17224 KB Output is correct
37 Correct 9 ms 17272 KB Output is correct
38 Correct 30 ms 17316 KB Output is correct
39 Correct 37 ms 17208 KB Output is correct
40 Correct 29 ms 17240 KB Output is correct
41 Correct 5 ms 17244 KB Output is correct
42 Correct 5 ms 17244 KB Output is correct
43 Correct 5 ms 17244 KB Output is correct
44 Correct 33 ms 17244 KB Output is correct
45 Correct 33 ms 17240 KB Output is correct
46 Correct 34 ms 17244 KB Output is correct
47 Correct 5 ms 17244 KB Output is correct
48 Correct 5 ms 17240 KB Output is correct
49 Correct 5 ms 17280 KB Output is correct
50 Correct 59 ms 17244 KB Output is correct
51 Correct 62 ms 17240 KB Output is correct
52 Correct 63 ms 17240 KB Output is correct
53 Correct 57 ms 17244 KB Output is correct
54 Correct 60 ms 17240 KB Output is correct
55 Correct 58 ms 17252 KB Output is correct
56 Correct 16 ms 16984 KB Output is correct
57 Correct 3 ms 16988 KB Output is correct
58 Correct 6 ms 17124 KB Output is correct
59 Correct 2 ms 16728 KB Output is correct
60 Correct 3 ms 16732 KB Output is correct
61 Correct 17 ms 16968 KB Output is correct
62 Execution timed out 5091 ms 31496 KB Time limit exceeded
63 Halted 0 ms 0 KB -