oj.uz

Submission #849296

# Submission time Handle Problem Language Result Execution time Memory
849296 2023-09-14T11:54:19 Z He_Huanglu Tourism (JOI23_tourism) C++17
100 / 100
 294 ms 118240 KB 
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;

const int N = 1e5 + 5, S = 18;
int n, m, q, timer;
int d[N], heavy[N], chain[N], sz[N], par[N], num[N], ans[N], sp[2 * N][S], g[N][S], c[N], bit[N], f[N], Left[N];
vector <int> ke[N], euler, A, val[N], lis[N];
stack <int> st[N];

void dfs(int u, int pre = 0) {
    int mx = 0;
    sz[u] = 1; heavy[u] = -1; num[u] = timer++;
    euler.push_back(u);
    A.push_back(d[u]);
    for(int v : ke[u]) if(v != pre) {
        sz[u] += sz[v];
        par[v] = u; d[v] = d[u] + 1;
        dfs(v, u);
        euler.push_back(u);
        A.push_back(d[u]);
        timer++;
        if(sz[v] > mx) {
            mx = sz[v];
            heavy[u] = v;
        }
    }
}

void dfss(int u, int pre = 0) {
    if(u == 1) f[u] = chain[u] = 1;
    for(int v : ke[u]) if(v != pre) {
        if(v == heavy[u]) {
            chain[v] = chain[u];
            f[v] = f[u] + 1;
        }
        else chain[v] = v, f[v] = 1;
        dfss(v, u);
    }
}

void upd(int x, int v) {
    for(; x <= m; x += (x & -x)) bit[x] += v;
}

void upds(int l, int r, int v) {
    upd(l, v);
    upd(r + 1, -v);
}

int get(int x) {
    int ret = 0;
    for(; x > 0; x -= (x & -x)) ret += bit[x];
    return ret;
}

void solve(int p, int v, int i) {
    upds(st[p].top() + 1, i, v);
    while (val[p].size() && v > val[p].back()) {
        int r = st[p].top(); st[p].pop();
        upds(st[p].top() + 1, r, v - val[p].back());
        val[p].pop_back();
    }
    st[p].push(i);
    val[p].push_back(v);
}

void jump(int i, int u) {
    while (u) {
        solve(chain[u], f[u], i);
        u = par[chain[u]];
    }
}

void init(int n) {
    for(int i = 0; i < n; i++) sp[i][0] = i;
    for(int j = 1; (1 << j) <= n; j++) {
        for(int i = 1; i + (1 << j) - 1 < n; i++) {
            int o = i + (1 << j - 1);
            if(A[sp[i][j - 1]] < A[sp[o][j - 1]]) {
                sp[i][j] = sp[i][j - 1];
            }
            else sp[i][j] = sp[o][j - 1];
        }
    }
}

int lca(int u, int v) {
    int l = min(num[u], num[v]), r = max(num[u], num[v]);
    int k = log2(r - l + 1);
    int i = sp[l][k], j = sp[r - (1 << k) + 1][k];
    return (A[i] < A[j]) ? euler[i] : euler[j];
}

void build() {
    for(int i = 1; i <= m; i++) g[i][0] = c[i];
    for(int j = 1; (1 << j) <= m; j++) {
        for(int i = 1; i + (1 << j) - 1 <= m; i++) {
            g[i][j] = lca(g[i][j - 1], g[i + (1 << j - 1)][j - 1]);
        }
    }
}

int get(int l, int r) {
    int k = log2(r - l + 1);
    return lca(g[l][k], g[r - (1 << k) + 1][k]);
}

main () {
    cin.tie(0)->sync_with_stdio(0);
    if(fopen("task.inp", "r")) {
        freopen("task.inp", "r", stdin);
        freopen("wa.out", "w", stdout);
    }
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++) st[i].push(0);
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        ke[u].push_back(v);
        ke[v].push_back(u);
    }
    for(int i = 1; i <= m; i++) cin >> c[i];
    for(int i = 1; i <= q; i++) {
        int r; cin >> Left[i] >> r;
        lis[r].push_back(i);
    }
    dfs(1);
    dfss(1);
    init(timer);
    build();
    for(int i = 1; i <= m; i++) {
        jump(i, c[i]);
        for(int j : lis[i]) ans[j] = get(Left[j]) - d[(get(Left[j], i))];
    }
    for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

Compilation message

tourism.cpp: In function 'void init(int)':
tourism.cpp:81:33: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   81 |             int o = i + (1 << j - 1);
      |                               ~~^~~
tourism.cpp: In function 'void build()':
tourism.cpp:101:54: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  101 |             g[i][j] = lca(g[i][j - 1], g[i + (1 << j - 1)][j - 1]);
      |                                                    ~~^~~
tourism.cpp: At global scope:
tourism.cpp:111:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  111 | main () {
      | ^~~~
tourism.cpp: In function 'int main()':
tourism.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen("wa.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 80464 KB Output is correct
2 Correct 39 ms 80468 KB Output is correct
3 Correct 37 ms 80464 KB Output is correct
4 Correct 37 ms 80460 KB Output is correct
5 Correct 39 ms 80420 KB Output is correct
6 Correct 39 ms 80464 KB Output is correct
7 Correct 38 ms 80464 KB Output is correct
8 Correct 42 ms 80460 KB Output is correct
9 Correct 37 ms 80684 KB Output is correct
10 Correct 41 ms 80464 KB Output is correct
11 Correct 41 ms 80472 KB Output is correct
12 Correct 42 ms 80472 KB Output is correct
13 Correct 41 ms 80464 KB Output is correct
14 Correct 41 ms 80556 KB Output is correct
15 Correct 42 ms 80464 KB Output is correct
16 Correct 41 ms 80456 KB Output is correct
17 Correct 45 ms 80476 KB Output is correct
18 Correct 43 ms 80464 KB Output is correct
19 Correct 41 ms 80636 KB Output is correct
20 Correct 41 ms 80468 KB Output is correct
21 Correct 38 ms 80720 KB Output is correct
22 Correct 38 ms 80464 KB Output is correct
23 Correct 37 ms 80464 KB Output is correct
24 Correct 38 ms 80472 KB Output is correct
25 Correct 38 ms 80544 KB Output is correct
26 Correct 38 ms 80464 KB Output is correct
27 Correct 41 ms 80464 KB Output is correct
28 Correct 49 ms 81116 KB Output is correct
29 Correct 37 ms 80476 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 80464 KB Output is correct
2 Correct 39 ms 80468 KB Output is correct
3 Correct 37 ms 80464 KB Output is correct
4 Correct 37 ms 80460 KB Output is correct
5 Correct 39 ms 80420 KB Output is correct
6 Correct 39 ms 80464 KB Output is correct
7 Correct 38 ms 80464 KB Output is correct
8 Correct 42 ms 80460 KB Output is correct
9 Correct 37 ms 80684 KB Output is correct
10 Correct 41 ms 80464 KB Output is correct
11 Correct 41 ms 80472 KB Output is correct
12 Correct 42 ms 80472 KB Output is correct
13 Correct 41 ms 80464 KB Output is correct
14 Correct 41 ms 80556 KB Output is correct
15 Correct 42 ms 80464 KB Output is correct
16 Correct 41 ms 80456 KB Output is correct
17 Correct 45 ms 80476 KB Output is correct
18 Correct 43 ms 80464 KB Output is correct
19 Correct 41 ms 80636 KB Output is correct
20 Correct 41 ms 80468 KB Output is correct
21 Correct 38 ms 80720 KB Output is correct
22 Correct 38 ms 80464 KB Output is correct
23 Correct 37 ms 80464 KB Output is correct
24 Correct 38 ms 80472 KB Output is correct
25 Correct 38 ms 80544 KB Output is correct
26 Correct 38 ms 80464 KB Output is correct
27 Correct 41 ms 80464 KB Output is correct
28 Correct 49 ms 81116 KB Output is correct
29 Correct 37 ms 80476 KB Output is correct
30 Correct 39 ms 80760 KB Output is correct
31 Correct 47 ms 80720 KB Output is correct
32 Correct 44 ms 80740 KB Output is correct
33 Correct 39 ms 80720 KB Output is correct
34 Correct 39 ms 80720 KB Output is correct
35 Correct 39 ms 80720 KB Output is correct
36 Correct 41 ms 80728 KB Output is correct
37 Correct 39 ms 80720 KB Output is correct
38 Correct 43 ms 80968 KB Output is correct
39 Correct 43 ms 80984 KB Output is correct
40 Correct 43 ms 80980 KB Output is correct
41 Correct 38 ms 80832 KB Output is correct
42 Correct 41 ms 80976 KB Output is correct
43 Correct 38 ms 80904 KB Output is correct
44 Correct 43 ms 80980 KB Output is correct
45 Correct 42 ms 80728 KB Output is correct
46 Correct 45 ms 80716 KB Output is correct
47 Correct 38 ms 80728 KB Output is correct
48 Correct 39 ms 80640 KB Output is correct
49 Correct 41 ms 80724 KB Output is correct
50 Correct 38 ms 80848 KB Output is correct
51 Correct 40 ms 80720 KB Output is correct
52 Correct 38 ms 80720 KB Output is correct
53 Correct 39 ms 80752 KB Output is correct
54 Correct 40 ms 80720 KB Output is correct
55 Correct 40 ms 80720 KB Output is correct
56 Correct 43 ms 80464 KB Output is correct
57 Correct 41 ms 80728 KB Output is correct
58 Correct 43 ms 80724 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 80464 KB Output is correct
2 Correct 41 ms 80476 KB Output is correct
3 Correct 40 ms 80728 KB Output is correct
4 Correct 121 ms 106692 KB Output is correct
5 Correct 115 ms 109604 KB Output is correct
6 Correct 130 ms 115384 KB Output is correct
7 Correct 158 ms 118172 KB Output is correct
8 Correct 162 ms 118200 KB Output is correct
9 Correct 159 ms 118028 KB Output is correct
10 Correct 157 ms 118240 KB Output is correct
11 Correct 166 ms 118200 KB Output is correct
12 Correct 145 ms 116840 KB Output is correct
13 Correct 148 ms 116944 KB Output is correct
14 Correct 155 ms 116964 KB Output is correct
15 Correct 91 ms 109508 KB Output is correct
16 Correct 163 ms 117864 KB Output is correct
17 Correct 88 ms 90816 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 80464 KB Output is correct
2 Correct 129 ms 97916 KB Output is correct
3 Correct 170 ms 100804 KB Output is correct
4 Correct 150 ms 103352 KB Output is correct
5 Correct 240 ms 108212 KB Output is correct
6 Correct 215 ms 108128 KB Output is correct
7 Correct 218 ms 108244 KB Output is correct
8 Correct 211 ms 108144 KB Output is correct
9 Correct 219 ms 108212 KB Output is correct
10 Correct 219 ms 108220 KB Output is correct
11 Correct 222 ms 108512 KB Output is correct
12 Correct 220 ms 108340 KB Output is correct
13 Correct 218 ms 108648 KB Output is correct
14 Correct 253 ms 109472 KB Output is correct
15 Correct 248 ms 112576 KB Output is correct
16 Correct 210 ms 108648 KB Output is correct
17 Correct 222 ms 108652 KB Output is correct
18 Correct 219 ms 108648 KB Output is correct
19 Correct 181 ms 107176 KB Output is correct
20 Correct 168 ms 106956 KB Output is correct
21 Correct 175 ms 106860 KB Output is correct
22 Correct 190 ms 107112 KB Output is correct
23 Correct 184 ms 107100 KB Output is correct
24 Correct 173 ms 107200 KB Output is correct
25 Correct 229 ms 108240 KB Output is correct
26 Correct 167 ms 107000 KB Output is correct
27 Correct 174 ms 107116 KB Output is correct
28 Correct 171 ms 107212 KB Output is correct
29 Correct 178 ms 107160 KB Output is correct
30 Correct 177 ms 107392 KB Output is correct
31 Correct 189 ms 107452 KB Output is correct
32 Correct 216 ms 107960 KB Output is correct
33 Correct 200 ms 109416 KB Output is correct
34 Correct 222 ms 112000 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 80464 KB Output is correct
2 Correct 41 ms 80464 KB Output is correct
3 Correct 40 ms 80728 KB Output is correct
4 Correct 207 ms 103580 KB Output is correct
5 Correct 237 ms 104060 KB Output is correct
6 Correct 248 ms 110264 KB Output is correct
7 Correct 281 ms 111636 KB Output is correct
8 Correct 293 ms 111628 KB Output is correct
9 Correct 274 ms 111676 KB Output is correct
10 Correct 294 ms 111900 KB Output is correct
11 Correct 264 ms 111548 KB Output is correct
12 Correct 291 ms 111580 KB Output is correct
13 Correct 271 ms 111548 KB Output is correct
14 Correct 97 ms 90936 KB Output is correct

Subtask #6
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 80464 KB Output is correct
2 Correct 39 ms 80468 KB Output is correct
3 Correct 37 ms 80464 KB Output is correct
4 Correct 37 ms 80460 KB Output is correct
5 Correct 39 ms 80420 KB Output is correct
6 Correct 39 ms 80464 KB Output is correct
7 Correct 38 ms 80464 KB Output is correct
8 Correct 42 ms 80460 KB Output is correct
9 Correct 37 ms 80684 KB Output is correct
10 Correct 41 ms 80464 KB Output is correct
11 Correct 41 ms 80472 KB Output is correct
12 Correct 42 ms 80472 KB Output is correct
13 Correct 41 ms 80464 KB Output is correct
14 Correct 41 ms 80556 KB Output is correct
15 Correct 42 ms 80464 KB Output is correct
16 Correct 41 ms 80456 KB Output is correct
17 Correct 45 ms 80476 KB Output is correct
18 Correct 43 ms 80464 KB Output is correct
19 Correct 41 ms 80636 KB Output is correct
20 Correct 41 ms 80468 KB Output is correct
21 Correct 38 ms 80720 KB Output is correct
22 Correct 38 ms 80464 KB Output is correct
23 Correct 37 ms 80464 KB Output is correct
24 Correct 38 ms 80472 KB Output is correct
25 Correct 38 ms 80544 KB Output is correct
26 Correct 38 ms 80464 KB Output is correct
27 Correct 41 ms 80464 KB Output is correct
28 Correct 49 ms 81116 KB Output is correct
29 Correct 37 ms 80476 KB Output is correct
30 Correct 39 ms 80760 KB Output is correct
31 Correct 47 ms 80720 KB Output is correct
32 Correct 44 ms 80740 KB Output is correct
33 Correct 39 ms 80720 KB Output is correct
34 Correct 39 ms 80720 KB Output is correct
35 Correct 39 ms 80720 KB Output is correct
36 Correct 41 ms 80728 KB Output is correct
37 Correct 39 ms 80720 KB Output is correct
38 Correct 43 ms 80968 KB Output is correct
39 Correct 43 ms 80984 KB Output is correct
40 Correct 43 ms 80980 KB Output is correct
41 Correct 38 ms 80832 KB Output is correct
42 Correct 41 ms 80976 KB Output is correct
43 Correct 38 ms 80904 KB Output is correct
44 Correct 43 ms 80980 KB Output is correct
45 Correct 42 ms 80728 KB Output is correct
46 Correct 45 ms 80716 KB Output is correct
47 Correct 38 ms 80728 KB Output is correct
48 Correct 39 ms 80640 KB Output is correct
49 Correct 41 ms 80724 KB Output is correct
50 Correct 38 ms 80848 KB Output is correct
51 Correct 40 ms 80720 KB Output is correct
52 Correct 38 ms 80720 KB Output is correct
53 Correct 39 ms 80752 KB Output is correct
54 Correct 40 ms 80720 KB Output is correct
55 Correct 40 ms 80720 KB Output is correct
56 Correct 43 ms 80464 KB Output is correct
57 Correct 41 ms 80728 KB Output is correct
58 Correct 43 ms 80724 KB Output is correct
59 Correct 37 ms 80464 KB Output is correct
60 Correct 41 ms 80476 KB Output is correct
61 Correct 40 ms 80728 KB Output is correct
62 Correct 121 ms 106692 KB Output is correct
63 Correct 115 ms 109604 KB Output is correct
64 Correct 130 ms 115384 KB Output is correct
65 Correct 158 ms 118172 KB Output is correct
66 Correct 162 ms 118200 KB Output is correct
67 Correct 159 ms 118028 KB Output is correct
68 Correct 157 ms 118240 KB Output is correct
69 Correct 166 ms 118200 KB Output is correct
70 Correct 145 ms 116840 KB Output is correct
71 Correct 148 ms 116944 KB Output is correct
72 Correct 155 ms 116964 KB Output is correct
73 Correct 91 ms 109508 KB Output is correct
74 Correct 163 ms 117864 KB Output is correct
75 Correct 88 ms 90816 KB Output is correct
76 Correct 47 ms 80464 KB Output is correct
77 Correct 129 ms 97916 KB Output is correct
78 Correct 170 ms 100804 KB Output is correct
79 Correct 150 ms 103352 KB Output is correct
80 Correct 240 ms 108212 KB Output is correct
81 Correct 215 ms 108128 KB Output is correct
82 Correct 218 ms 108244 KB Output is correct
83 Correct 211 ms 108144 KB Output is correct
84 Correct 219 ms 108212 KB Output is correct
85 Correct 219 ms 108220 KB Output is correct
86 Correct 222 ms 108512 KB Output is correct
87 Correct 220 ms 108340 KB Output is correct
88 Correct 218 ms 108648 KB Output is correct
89 Correct 253 ms 109472 KB Output is correct
90 Correct 248 ms 112576 KB Output is correct
91 Correct 210 ms 108648 KB Output is correct
92 Correct 222 ms 108652 KB Output is correct
93 Correct 219 ms 108648 KB Output is correct
94 Correct 181 ms 107176 KB Output is correct
95 Correct 168 ms 106956 KB Output is correct
96 Correct 175 ms 106860 KB Output is correct
97 Correct 190 ms 107112 KB Output is correct
98 Correct 184 ms 107100 KB Output is correct
99 Correct 173 ms 107200 KB Output is correct
100 Correct 229 ms 108240 KB Output is correct
101 Correct 167 ms 107000 KB Output is correct
102 Correct 174 ms 107116 KB Output is correct
103 Correct 171 ms 107212 KB Output is correct
104 Correct 178 ms 107160 KB Output is correct
105 Correct 177 ms 107392 KB Output is correct
106 Correct 189 ms 107452 KB Output is correct
107 Correct 216 ms 107960 KB Output is correct
108 Correct 200 ms 109416 KB Output is correct
109 Correct 222 ms 112000 KB Output is correct
110 Correct 37 ms 80464 KB Output is correct
111 Correct 41 ms 80464 KB Output is correct
112 Correct 40 ms 80728 KB Output is correct
113 Correct 207 ms 103580 KB Output is correct
114 Correct 237 ms 104060 KB Output is correct
115 Correct 248 ms 110264 KB Output is correct
116 Correct 281 ms 111636 KB Output is correct
117 Correct 293 ms 111628 KB Output is correct
118 Correct 274 ms 111676 KB Output is correct
119 Correct 294 ms 111900 KB Output is correct
120 Correct 264 ms 111548 KB Output is correct
121 Correct 291 ms 111580 KB Output is correct
122 Correct 271 ms 111548 KB Output is correct
123 Correct 97 ms 90936 KB Output is correct
124 Correct 265 ms 111464 KB Output is correct
125 Correct 192 ms 109476 KB Output is correct
126 Correct 280 ms 111984 KB Output is correct
127 Correct 266 ms 111856 KB Output is correct
128 Correct 276 ms 111796 KB Output is correct
129 Correct 289 ms 111736 KB Output is correct
130 Correct 271 ms 111684 KB Output is correct
131 Correct 169 ms 117348 KB Output is correct
132 Correct 166 ms 117944 KB Output is correct
133 Correct 163 ms 114344 KB Output is correct
134 Correct 215 ms 110520 KB Output is correct
135 Correct 241 ms 110816 KB Output is correct
136 Correct 224 ms 110524 KB Output is correct
137 Correct 194 ms 113096 KB Output is correct
138 Correct 221 ms 113376 KB Output is correct
139 Correct 193 ms 113372 KB Output is correct
140 Correct 190 ms 113092 KB Output is correct
141 Correct 207 ms 113412 KB Output is correct
142 Correct 217 ms 113272 KB Output is correct
143 Correct 99 ms 101812 KB Output is correct
144 Correct 277 ms 111544 KB Output is correct