oj.uz

Submission #1117222

# Submission time Handle Problem Language Result Execution time Memory
1117222 2024-11-23T02:34:22 Z hqminhuwu Tourism (JOI23_tourism) C++14
100 / 100
 773 ms 46492 KB 
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

template<class X, class Y>
    bool minz(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } return false;
    }
template<class X, class Y>
    bool maxz(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }

const int N = 5e5 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;

int n, m, bit[N], pos[N], head[N], sz[N], hv[N], u, v, q, cnt, dep[N], c[N], p[N];
vector <int> a[N];
vector <pii> qq[N];

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

int get (int i){
    int res = 0;
    for (; i; i -= i & -i)
        res += bit[i];
    return res;
}

void dfsz (int u){
    sz[u] = 1;
    for (int v : a[u]){
        if (sz[v]) continue;
        dep[v] = dep[u] + 1;
        p[v] = u;
        dfsz(v);
        sz[u] += sz[v];
        if (sz[v] > sz[hv[u]]){
            hv[u] = v;
        }
    }
}

void dcp (int u, int h){
    head[u] = h;
    pos[u] = ++cnt;
    
    if (hv[u]){
        dcp(hv[u], h);
    }

    for (int v : a[u]){
        if (sz[v] > sz[u] || v == hv[u]) continue;
        dcp(v, v);
    }
}

set <piii> s;

void uwu (int l, int r, int val){
	auto it = s.lower_bound({l, {l, 0}});
	
    if(it != s.begin()) it--;
	vector <piii> rem, add;
    add.pb({l, {r, val}});

	for (; it != s.end() && (*it).st <= r; ++it){
		int fl = (*it).st, fr = (*it).nd.st, fv = (*it).nd.nd;
		if(fr < l) continue;
		rem.pb(*it);
		if(fl < l) add.pb({fl, {l - 1, fv}});
		if(fr > r) add.pb({r + 1, {fr, fv}});
	}

	for (piii x : rem){
		upd(x.nd.nd, -(x.nd.st - x.st + 1));
		s.erase(x);
	}

	for(piii x : add){
		upd(x.nd.nd, x.nd.st - x.st + 1);
		s.insert(x);
	}
}

void owo (int u, int v, int val){
    for (; head[u] != head[v]; v = p[head[v]]){
        if (dep[head[u]] > dep[head[v]])
            swap(u, v);
        uwu(pos[head[v]], pos[v], val);
    }
    if (dep[u] > dep[v])
        swap(u, v);
    uwu(pos[u], pos[v], val);
}


int ans[N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef kaguya
        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif

    cin >> n >> m >> q;

    forf (i, 1, n){
        cin >> u >> v;
        a[u].pb(v);
        a[v].pb(u);
    }

    dfsz(1);
    dcp(1, 1);

    forr (i, 1, m){
        cin >> c[i];
    }

    forr (i, 1, q){
        cin >> u >> v;
        qq[v].pb({u, i});
    }    

    forr (i, 1, m){
        if (i > 1){
            owo(c[i], c[i - 1], i);
        }

        for (pii t : qq[i]){
            if (t.st == i){
                ans[t.nd] = 1;
            } else {
                ans[t.nd] = get(i) - get(t.st);
            }
        }
    }

    forr (i, 1, q){
        cout << ans[i] << "\n";
    }


    

    return 0;
}
/*



*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35152 KB Output is correct
2 Correct 5 ms 31224 KB Output is correct
3 Correct 5 ms 35152 KB Output is correct
4 Correct 5 ms 27384 KB Output is correct
5 Correct 5 ms 27216 KB Output is correct
6 Correct 9 ms 27216 KB Output is correct
7 Correct 10 ms 27216 KB Output is correct
8 Correct 9 ms 27216 KB Output is correct
9 Correct 9 ms 27128 KB Output is correct
10 Correct 11 ms 25424 KB Output is correct
11 Correct 7 ms 27216 KB Output is correct
12 Correct 10 ms 27216 KB Output is correct
13 Correct 11 ms 27088 KB Output is correct
14 Correct 9 ms 27216 KB Output is correct
15 Correct 12 ms 27216 KB Output is correct
16 Correct 7 ms 27216 KB Output is correct
17 Correct 9 ms 27216 KB Output is correct
18 Correct 10 ms 27216 KB Output is correct
19 Correct 9 ms 27216 KB Output is correct
20 Correct 11 ms 27216 KB Output is correct
21 Correct 8 ms 27216 KB Output is correct
22 Correct 11 ms 27092 KB Output is correct
23 Correct 9 ms 27092 KB Output is correct
24 Correct 10 ms 27216 KB Output is correct
25 Correct 11 ms 25424 KB Output is correct
26 Correct 11 ms 27216 KB Output is correct
27 Correct 11 ms 25424 KB Output is correct
28 Correct 10 ms 27216 KB Output is correct
29 Correct 9 ms 27216 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35152 KB Output is correct
2 Correct 5 ms 31224 KB Output is correct
3 Correct 5 ms 35152 KB Output is correct
4 Correct 5 ms 27384 KB Output is correct
5 Correct 5 ms 27216 KB Output is correct
6 Correct 9 ms 27216 KB Output is correct
7 Correct 10 ms 27216 KB Output is correct
8 Correct 9 ms 27216 KB Output is correct
9 Correct 9 ms 27128 KB Output is correct
10 Correct 11 ms 25424 KB Output is correct
11 Correct 7 ms 27216 KB Output is correct
12 Correct 10 ms 27216 KB Output is correct
13 Correct 11 ms 27088 KB Output is correct
14 Correct 9 ms 27216 KB Output is correct
15 Correct 12 ms 27216 KB Output is correct
16 Correct 7 ms 27216 KB Output is correct
17 Correct 9 ms 27216 KB Output is correct
18 Correct 10 ms 27216 KB Output is correct
19 Correct 9 ms 27216 KB Output is correct
20 Correct 11 ms 27216 KB Output is correct
21 Correct 8 ms 27216 KB Output is correct
22 Correct 11 ms 27092 KB Output is correct
23 Correct 9 ms 27092 KB Output is correct
24 Correct 10 ms 27216 KB Output is correct
25 Correct 11 ms 25424 KB Output is correct
26 Correct 11 ms 27216 KB Output is correct
27 Correct 11 ms 25424 KB Output is correct
28 Correct 10 ms 27216 KB Output is correct
29 Correct 9 ms 27216 KB Output is correct
30 Correct 11 ms 27216 KB Output is correct
31 Correct 10 ms 27384 KB Output is correct
32 Correct 12 ms 27472 KB Output is correct
33 Correct 11 ms 27472 KB Output is correct
34 Correct 11 ms 27472 KB Output is correct
35 Correct 10 ms 27256 KB Output is correct
36 Correct 15 ms 27408 KB Output is correct
37 Correct 13 ms 27216 KB Output is correct
38 Correct 12 ms 25680 KB Output is correct
39 Correct 12 ms 24144 KB Output is correct
40 Correct 10 ms 27472 KB Output is correct
41 Correct 8 ms 27472 KB Output is correct
42 Correct 8 ms 27340 KB Output is correct
43 Correct 12 ms 27472 KB Output is correct
44 Correct 12 ms 27472 KB Output is correct
45 Correct 15 ms 24144 KB Output is correct
46 Correct 10 ms 27472 KB Output is correct
47 Correct 10 ms 27452 KB Output is correct
48 Correct 10 ms 27216 KB Output is correct
49 Correct 10 ms 27352 KB Output is correct
50 Correct 9 ms 27472 KB Output is correct
51 Correct 8 ms 27360 KB Output is correct
52 Correct 9 ms 27496 KB Output is correct
53 Correct 10 ms 27472 KB Output is correct
54 Correct 11 ms 27348 KB Output is correct
55 Correct 11 ms 27488 KB Output is correct
56 Correct 9 ms 27216 KB Output is correct
57 Correct 6 ms 27216 KB Output is correct
58 Correct 11 ms 27472 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 26960 KB Output is correct
2 Correct 10 ms 25304 KB Output is correct
3 Correct 10 ms 23880 KB Output is correct
4 Correct 94 ms 36516 KB Output is correct
5 Correct 73 ms 41832 KB Output is correct
6 Correct 87 ms 43336 KB Output is correct
7 Correct 109 ms 46408 KB Output is correct
8 Correct 109 ms 46404 KB Output is correct
9 Correct 112 ms 46492 KB Output is correct
10 Correct 113 ms 46408 KB Output is correct
11 Correct 111 ms 46256 KB Output is correct
12 Correct 102 ms 45896 KB Output is correct
13 Correct 101 ms 45816 KB Output is correct
14 Correct 102 ms 45896 KB Output is correct
15 Correct 46 ms 44440 KB Output is correct
16 Correct 116 ms 46164 KB Output is correct
17 Correct 61 ms 31568 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 26960 KB Output is correct
2 Correct 235 ms 32512 KB Output is correct
3 Correct 366 ms 34396 KB Output is correct
4 Correct 283 ms 34632 KB Output is correct
5 Correct 456 ms 38220 KB Output is correct
6 Correct 469 ms 38216 KB Output is correct
7 Correct 469 ms 36384 KB Output is correct
8 Correct 446 ms 38216 KB Output is correct
9 Correct 461 ms 38000 KB Output is correct
10 Correct 443 ms 38216 KB Output is correct
11 Correct 432 ms 38216 KB Output is correct
12 Correct 431 ms 38284 KB Output is correct
13 Correct 452 ms 38556 KB Output is correct
14 Correct 462 ms 41288 KB Output is correct
15 Correct 468 ms 42824 KB Output is correct
16 Correct 430 ms 38520 KB Output is correct
17 Correct 474 ms 38480 KB Output is correct
18 Correct 452 ms 38472 KB Output is correct
19 Correct 293 ms 35144 KB Output is correct
20 Correct 277 ms 35144 KB Output is correct
21 Correct 328 ms 35144 KB Output is correct
22 Correct 292 ms 35144 KB Output is correct
23 Correct 290 ms 35116 KB Output is correct
24 Correct 290 ms 35144 KB Output is correct
25 Correct 285 ms 35144 KB Output is correct
26 Correct 303 ms 35144 KB Output is correct
27 Correct 277 ms 35188 KB Output is correct
28 Correct 304 ms 35144 KB Output is correct
29 Correct 275 ms 35212 KB Output is correct
30 Correct 276 ms 35400 KB Output is correct
31 Correct 278 ms 35656 KB Output is correct
32 Correct 278 ms 36180 KB Output is correct
33 Correct 331 ms 37448 KB Output is correct
34 Correct 290 ms 39892 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 26960 KB Output is correct
2 Correct 6 ms 26960 KB Output is correct
3 Correct 7 ms 27264 KB Output is correct
4 Correct 621 ms 35520 KB Output is correct
5 Correct 650 ms 35720 KB Output is correct
6 Correct 756 ms 37944 KB Output is correct
7 Correct 766 ms 40936 KB Output is correct
8 Correct 743 ms 39240 KB Output is correct
9 Correct 773 ms 41288 KB Output is correct
10 Correct 760 ms 39496 KB Output is correct
11 Correct 755 ms 41032 KB Output is correct
12 Correct 718 ms 39384 KB Output is correct
13 Correct 733 ms 39424 KB Output is correct
14 Correct 41 ms 30288 KB Output is correct

Subtask #6
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35152 KB Output is correct
2 Correct 5 ms 31224 KB Output is correct
3 Correct 5 ms 35152 KB Output is correct
4 Correct 5 ms 27384 KB Output is correct
5 Correct 5 ms 27216 KB Output is correct
6 Correct 9 ms 27216 KB Output is correct
7 Correct 10 ms 27216 KB Output is correct
8 Correct 9 ms 27216 KB Output is correct
9 Correct 9 ms 27128 KB Output is correct
10 Correct 11 ms 25424 KB Output is correct
11 Correct 7 ms 27216 KB Output is correct
12 Correct 10 ms 27216 KB Output is correct
13 Correct 11 ms 27088 KB Output is correct
14 Correct 9 ms 27216 KB Output is correct
15 Correct 12 ms 27216 KB Output is correct
16 Correct 7 ms 27216 KB Output is correct
17 Correct 9 ms 27216 KB Output is correct
18 Correct 10 ms 27216 KB Output is correct
19 Correct 9 ms 27216 KB Output is correct
20 Correct 11 ms 27216 KB Output is correct
21 Correct 8 ms 27216 KB Output is correct
22 Correct 11 ms 27092 KB Output is correct
23 Correct 9 ms 27092 KB Output is correct
24 Correct 10 ms 27216 KB Output is correct
25 Correct 11 ms 25424 KB Output is correct
26 Correct 11 ms 27216 KB Output is correct
27 Correct 11 ms 25424 KB Output is correct
28 Correct 10 ms 27216 KB Output is correct
29 Correct 9 ms 27216 KB Output is correct
30 Correct 11 ms 27216 KB Output is correct
31 Correct 10 ms 27384 KB Output is correct
32 Correct 12 ms 27472 KB Output is correct
33 Correct 11 ms 27472 KB Output is correct
34 Correct 11 ms 27472 KB Output is correct
35 Correct 10 ms 27256 KB Output is correct
36 Correct 15 ms 27408 KB Output is correct
37 Correct 13 ms 27216 KB Output is correct
38 Correct 12 ms 25680 KB Output is correct
39 Correct 12 ms 24144 KB Output is correct
40 Correct 10 ms 27472 KB Output is correct
41 Correct 8 ms 27472 KB Output is correct
42 Correct 8 ms 27340 KB Output is correct
43 Correct 12 ms 27472 KB Output is correct
44 Correct 12 ms 27472 KB Output is correct
45 Correct 15 ms 24144 KB Output is correct
46 Correct 10 ms 27472 KB Output is correct
47 Correct 10 ms 27452 KB Output is correct
48 Correct 10 ms 27216 KB Output is correct
49 Correct 10 ms 27352 KB Output is correct
50 Correct 9 ms 27472 KB Output is correct
51 Correct 8 ms 27360 KB Output is correct
52 Correct 9 ms 27496 KB Output is correct
53 Correct 10 ms 27472 KB Output is correct
54 Correct 11 ms 27348 KB Output is correct
55 Correct 11 ms 27488 KB Output is correct
56 Correct 9 ms 27216 KB Output is correct
57 Correct 6 ms 27216 KB Output is correct
58 Correct 11 ms 27472 KB Output is correct
59 Correct 8 ms 26960 KB Output is correct
60 Correct 10 ms 25304 KB Output is correct
61 Correct 10 ms 23880 KB Output is correct
62 Correct 94 ms 36516 KB Output is correct
63 Correct 73 ms 41832 KB Output is correct
64 Correct 87 ms 43336 KB Output is correct
65 Correct 109 ms 46408 KB Output is correct
66 Correct 109 ms 46404 KB Output is correct
67 Correct 112 ms 46492 KB Output is correct
68 Correct 113 ms 46408 KB Output is correct
69 Correct 111 ms 46256 KB Output is correct
70 Correct 102 ms 45896 KB Output is correct
71 Correct 101 ms 45816 KB Output is correct
72 Correct 102 ms 45896 KB Output is correct
73 Correct 46 ms 44440 KB Output is correct
74 Correct 116 ms 46164 KB Output is correct
75 Correct 61 ms 31568 KB Output is correct
76 Correct 7 ms 26960 KB Output is correct
77 Correct 235 ms 32512 KB Output is correct
78 Correct 366 ms 34396 KB Output is correct
79 Correct 283 ms 34632 KB Output is correct
80 Correct 456 ms 38220 KB Output is correct
81 Correct 469 ms 38216 KB Output is correct
82 Correct 469 ms 36384 KB Output is correct
83 Correct 446 ms 38216 KB Output is correct
84 Correct 461 ms 38000 KB Output is correct
85 Correct 443 ms 38216 KB Output is correct
86 Correct 432 ms 38216 KB Output is correct
87 Correct 431 ms 38284 KB Output is correct
88 Correct 452 ms 38556 KB Output is correct
89 Correct 462 ms 41288 KB Output is correct
90 Correct 468 ms 42824 KB Output is correct
91 Correct 430 ms 38520 KB Output is correct
92 Correct 474 ms 38480 KB Output is correct
93 Correct 452 ms 38472 KB Output is correct
94 Correct 293 ms 35144 KB Output is correct
95 Correct 277 ms 35144 KB Output is correct
96 Correct 328 ms 35144 KB Output is correct
97 Correct 292 ms 35144 KB Output is correct
98 Correct 290 ms 35116 KB Output is correct
99 Correct 290 ms 35144 KB Output is correct
100 Correct 285 ms 35144 KB Output is correct
101 Correct 303 ms 35144 KB Output is correct
102 Correct 277 ms 35188 KB Output is correct
103 Correct 304 ms 35144 KB Output is correct
104 Correct 275 ms 35212 KB Output is correct
105 Correct 276 ms 35400 KB Output is correct
106 Correct 278 ms 35656 KB Output is correct
107 Correct 278 ms 36180 KB Output is correct
108 Correct 331 ms 37448 KB Output is correct
109 Correct 290 ms 39892 KB Output is correct
110 Correct 7 ms 26960 KB Output is correct
111 Correct 6 ms 26960 KB Output is correct
112 Correct 7 ms 27264 KB Output is correct
113 Correct 621 ms 35520 KB Output is correct
114 Correct 650 ms 35720 KB Output is correct
115 Correct 756 ms 37944 KB Output is correct
116 Correct 766 ms 40936 KB Output is correct
117 Correct 743 ms 39240 KB Output is correct
118 Correct 773 ms 41288 KB Output is correct
119 Correct 760 ms 39496 KB Output is correct
120 Correct 755 ms 41032 KB Output is correct
121 Correct 718 ms 39384 KB Output is correct
122 Correct 733 ms 39424 KB Output is correct
123 Correct 41 ms 30288 KB Output is correct
124 Correct 385 ms 41392 KB Output is correct
125 Correct 321 ms 39004 KB Output is correct
126 Correct 513 ms 42056 KB Output is correct
127 Correct 521 ms 42056 KB Output is correct
128 Correct 509 ms 41960 KB Output is correct
129 Correct 508 ms 41924 KB Output is correct
130 Correct 483 ms 40368 KB Output is correct
131 Correct 122 ms 45160 KB Output is correct
132 Correct 131 ms 46248 KB Output is correct
133 Correct 124 ms 44104 KB Output is correct
134 Correct 327 ms 40716 KB Output is correct
135 Correct 314 ms 42316 KB Output is correct
136 Correct 334 ms 38992 KB Output is correct
137 Correct 171 ms 42432 KB Output is correct
138 Correct 184 ms 42396 KB Output is correct
139 Correct 194 ms 42432 KB Output is correct
140 Correct 169 ms 42944 KB Output is correct
141 Correct 172 ms 42832 KB Output is correct
142 Correct 197 ms 43092 KB Output is correct
143 Correct 46 ms 35096 KB Output is correct
144 Correct 456 ms 41724 KB Output is correct