oj.uz

Submission #806990

# Submission time Handle Problem Language Result Execution time Memory
806990 2023-08-04T12:02:03 Z lukameladze Tourism (JOI23_tourism) C++17
100 / 100
 923 ms 53484 KB 
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//#define int long long
#define ll long long
#define pii pair <int, int>
#define pb push_back
#define ai3 array <int, 3>
const int N = 3e5 + 5;
int n, m, q,in[N], a[N], out[N], tin, lv[N], par[N][20];
vector <int> v[N];
vector < pii > updates;
void dfs(int a, int p) {
    in[a] = ++tin;
    lv[a] = lv[p] + 1;
    par[a][0] = p;
    for (int i = 1; i <= 18; i++) {
        par[a][i] = par[par[a][i - 1]][i - 1];
    }
    for (int to : v[a]) {
        if (to == p) continue;
        dfs(to, a);
    }
    out[a] = tin;
}
int upper(int a, int b) {
    return (in[a] <= in[b] && out[a] >= out[b]);
}
int lca(int a, int b) {
    if (upper(a, b)) return a;
    for (int i = 18; i >= 0; i--) {
        if (par[a][i] && !upper(par[a][i], b)) a = par[a][i];
    }
    return par[a][0];
}
bool cmp(int a, int b) {
    return in[a] < in[b];
}
int parent[N], added[N],added1[N];
vector <int> g[N];
void dfs1(int a, int p) {
    parent[a] = p;
    for (int to : g[a]) {
        if (to == p) continue;
        dfs1(to, a);
    }
}
int tree[N]; 
void upd(int idx, int val) {
    if (val > 0)
    updates.pb({idx, val});
    for (int i = idx; i < N; i+=i&(-i)) {
        tree[i] += val;
    }
}
int getans(int idx) {
    int pas = 0;
    for (int i = idx; i > 0; i-=i&(-i)) {
        pas += tree[i];
    }
    return pas;
}
vector <ai3> cur_q[N];
int sum[N], ans[N];
void solve(int l, int r, vector <ai3> que) {
    if (l > r || !que.size()) return ;
    vector <ai3> quel, quer;
    int mid = (l + r) / 2;
    
    for (ai3 sth : que) {
        if (sth[0] > mid) quer.pb(sth);
        else if (sth[1] <= mid) quel.pb(sth);
        else cur_q[sth[1]].pb(sth);
    }
    // building virtual tree, (not the most efficient way)
    vector <int> vert, fv;
    for (int i = l; i <= r; i++) {
        vert.pb(a[i]);
    }
    // remove duplicates, sort by in
    sort(vert.begin(), vert.end()); vert.resize(unique(vert.begin(), vert.end()) - vert.begin()); sort(vert.begin(), vert.end(), cmp);
    int sz = (int)vert.size();
    for (int i = 1; i < sz; i++) {
        vert.pb(lca(vert[i - 1], vert[i]));
    }
    sort(vert.begin(), vert.end()); vert.resize(unique(vert.begin(), vert.end()) - vert.begin()); sort(vert.begin(), vert.end(), cmp);
    for (int i = 1; i < (int)vert.size(); i++) { // Virtual tree edges
        int lc = lca(vert[i - 1], vert[i]);  
        g[lc].pb(vert[i]); g[vert[i]].pb(lc);
    }
    dfs1(a[mid], 0);
    for (int x : vert) {
        added[x] = 0; added1[x] = 0;
    }
    sum[mid] = 0;  added[a[mid]] = added1[a[mid]] = mid;
    for (int i = mid - 1; i >= l; i--) {
        int cur = a[i]; int vl = 0;
        //if (l == 4 && r == 6) cout<<"--- "<<i<<"\n";
        while (!added[cur]) {
            added[cur] = i;
          //  if (l == 4 && r == 6) cout<<cur<<" "<<parent[cur]<<" "<<abs(lv[cur] - lv[parent[cur]])<<"\n";
            vl += abs(lv[cur] - lv[parent[cur]]);
            cur = parent[cur];
        }
        sum[i] = sum[i + 1] + vl;
    }
    for (int i = mid + 1; i <= r; i++) {
        int cur = a[i];
        while (!added1[cur]) {
            if (added[cur] != mid) upd(added[cur] + 1, abs(lv[cur] - lv[parent[cur]]));
            added1[cur] = i;
            cur = parent[cur];
        }
        for (ai3 sth : cur_q[i]) {
            ans[sth[2]] = getans(sth[0]) + sum[sth[0]];
        }
        cur_q[i].clear();
    }
    for (pii sth : updates) {
        upd(sth.f, -sth.s);
    }
    updates.clear();
    for (int x : vert) g[x].clear();
    solve(l, mid, quel);
    solve(mid + 1, r, quer);
}
signed main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m>>q;
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
    }
    dfs(1, 0);
    for (int i = 1; i <= m; i++) {
        cin>>a[i];
    }
    vector < ai3 > queries;
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin>>l>>r;
        if (l == r) ans[i] = 0;
        else
        queries.pb({l, r, i});
    }
    solve(1, m, queries);
    for (int i = 1; i <= q; i++) {
        cout<<ans[i] + 1<<"\n";
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21460 KB Output is correct
2 Correct 13 ms 21520 KB Output is correct
3 Correct 11 ms 21460 KB Output is correct
4 Correct 11 ms 21588 KB Output is correct
5 Correct 11 ms 21588 KB Output is correct
6 Correct 11 ms 21588 KB Output is correct
7 Correct 12 ms 21524 KB Output is correct
8 Correct 12 ms 21588 KB Output is correct
9 Correct 12 ms 21592 KB Output is correct
10 Correct 10 ms 21556 KB Output is correct
11 Correct 11 ms 21588 KB Output is correct
12 Correct 10 ms 21588 KB Output is correct
13 Correct 10 ms 21588 KB Output is correct
14 Correct 10 ms 21588 KB Output is correct
15 Correct 14 ms 21544 KB Output is correct
16 Correct 10 ms 21588 KB Output is correct
17 Correct 10 ms 21588 KB Output is correct
18 Correct 12 ms 21588 KB Output is correct
19 Correct 11 ms 21588 KB Output is correct
20 Correct 11 ms 21644 KB Output is correct
21 Correct 12 ms 21588 KB Output is correct
22 Correct 9 ms 21588 KB Output is correct
23 Correct 10 ms 21588 KB Output is correct
24 Correct 10 ms 21588 KB Output is correct
25 Correct 11 ms 21640 KB Output is correct
26 Correct 10 ms 21588 KB Output is correct
27 Correct 10 ms 21480 KB Output is correct
28 Correct 12 ms 21484 KB Output is correct
29 Correct 11 ms 21460 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21460 KB Output is correct
2 Correct 13 ms 21520 KB Output is correct
3 Correct 11 ms 21460 KB Output is correct
4 Correct 11 ms 21588 KB Output is correct
5 Correct 11 ms 21588 KB Output is correct
6 Correct 11 ms 21588 KB Output is correct
7 Correct 12 ms 21524 KB Output is correct
8 Correct 12 ms 21588 KB Output is correct
9 Correct 12 ms 21592 KB Output is correct
10 Correct 10 ms 21556 KB Output is correct
11 Correct 11 ms 21588 KB Output is correct
12 Correct 10 ms 21588 KB Output is correct
13 Correct 10 ms 21588 KB Output is correct
14 Correct 10 ms 21588 KB Output is correct
15 Correct 14 ms 21544 KB Output is correct
16 Correct 10 ms 21588 KB Output is correct
17 Correct 10 ms 21588 KB Output is correct
18 Correct 12 ms 21588 KB Output is correct
19 Correct 11 ms 21588 KB Output is correct
20 Correct 11 ms 21644 KB Output is correct
21 Correct 12 ms 21588 KB Output is correct
22 Correct 9 ms 21588 KB Output is correct
23 Correct 10 ms 21588 KB Output is correct
24 Correct 10 ms 21588 KB Output is correct
25 Correct 11 ms 21640 KB Output is correct
26 Correct 10 ms 21588 KB Output is correct
27 Correct 10 ms 21480 KB Output is correct
28 Correct 12 ms 21484 KB Output is correct
29 Correct 11 ms 21460 KB Output is correct
30 Correct 14 ms 21844 KB Output is correct
31 Correct 14 ms 21944 KB Output is correct
32 Correct 16 ms 21972 KB Output is correct
33 Correct 16 ms 22060 KB Output is correct
34 Correct 15 ms 22068 KB Output is correct
35 Correct 12 ms 21972 KB Output is correct
36 Correct 12 ms 21972 KB Output is correct
37 Correct 12 ms 21972 KB Output is correct
38 Correct 17 ms 22012 KB Output is correct
39 Correct 15 ms 22108 KB Output is correct
40 Correct 15 ms 22108 KB Output is correct
41 Correct 12 ms 22080 KB Output is correct
42 Correct 12 ms 22100 KB Output is correct
43 Correct 13 ms 22024 KB Output is correct
44 Correct 18 ms 21972 KB Output is correct
45 Correct 16 ms 22052 KB Output is correct
46 Correct 15 ms 22084 KB Output is correct
47 Correct 14 ms 21972 KB Output is correct
48 Correct 12 ms 21972 KB Output is correct
49 Correct 13 ms 21936 KB Output is correct
50 Correct 15 ms 22008 KB Output is correct
51 Correct 16 ms 22024 KB Output is correct
52 Correct 15 ms 21972 KB Output is correct
53 Correct 14 ms 21972 KB Output is correct
54 Correct 17 ms 22076 KB Output is correct
55 Correct 14 ms 21972 KB Output is correct
56 Correct 11 ms 21588 KB Output is correct
57 Correct 11 ms 21712 KB Output is correct
58 Correct 13 ms 21716 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21560 KB Output is correct
2 Correct 10 ms 21460 KB Output is correct
3 Correct 10 ms 21588 KB Output is correct
4 Correct 255 ms 39836 KB Output is correct
5 Correct 184 ms 43424 KB Output is correct
6 Correct 259 ms 45832 KB Output is correct
7 Correct 324 ms 53328 KB Output is correct
8 Correct 329 ms 53304 KB Output is correct
9 Correct 324 ms 53324 KB Output is correct
10 Correct 330 ms 53432 KB Output is correct
11 Correct 332 ms 53484 KB Output is correct
12 Correct 108 ms 50148 KB Output is correct
13 Correct 90 ms 50116 KB Output is correct
14 Correct 91 ms 50132 KB Output is correct
15 Correct 72 ms 40432 KB Output is correct
16 Correct 83 ms 42044 KB Output is correct
17 Correct 64 ms 30464 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21460 KB Output is correct
2 Correct 353 ms 31884 KB Output is correct
3 Correct 598 ms 35052 KB Output is correct
4 Correct 412 ms 35380 KB Output is correct
5 Correct 119 ms 40932 KB Output is correct
6 Correct 194 ms 41676 KB Output is correct
7 Correct 268 ms 41896 KB Output is correct
8 Correct 374 ms 42064 KB Output is correct
9 Correct 439 ms 42036 KB Output is correct
10 Correct 588 ms 41980 KB Output is correct
11 Correct 670 ms 42092 KB Output is correct
12 Correct 785 ms 42332 KB Output is correct
13 Correct 816 ms 42964 KB Output is correct
14 Correct 831 ms 44636 KB Output is correct
15 Correct 92 ms 37636 KB Output is correct
16 Correct 528 ms 43220 KB Output is correct
17 Correct 539 ms 43200 KB Output is correct
18 Correct 565 ms 43292 KB Output is correct
19 Correct 105 ms 40644 KB Output is correct
20 Correct 129 ms 41100 KB Output is correct
21 Correct 161 ms 41620 KB Output is correct
22 Correct 212 ms 41752 KB Output is correct
23 Correct 250 ms 41732 KB Output is correct
24 Correct 310 ms 41704 KB Output is correct
25 Correct 377 ms 41712 KB Output is correct
26 Correct 437 ms 41836 KB Output is correct
27 Correct 540 ms 41716 KB Output is correct
28 Correct 610 ms 41776 KB Output is correct
29 Correct 681 ms 41900 KB Output is correct
30 Correct 755 ms 42232 KB Output is correct
31 Correct 789 ms 42740 KB Output is correct
32 Correct 916 ms 43860 KB Output is correct
33 Correct 923 ms 45076 KB Output is correct
34 Correct 77 ms 37532 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21456 KB Output is correct
2 Correct 10 ms 21540 KB Output is correct
3 Correct 11 ms 21688 KB Output is correct
4 Correct 419 ms 38664 KB Output is correct
5 Correct 433 ms 38604 KB Output is correct
6 Correct 515 ms 43668 KB Output is correct
7 Correct 535 ms 46272 KB Output is correct
8 Correct 535 ms 46180 KB Output is correct
9 Correct 549 ms 46164 KB Output is correct
10 Correct 539 ms 46088 KB Output is correct
11 Correct 559 ms 46180 KB Output is correct
12 Correct 546 ms 46216 KB Output is correct
13 Correct 589 ms 46160 KB Output is correct
14 Correct 53 ms 29016 KB Output is correct

Subtask #6
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21460 KB Output is correct
2 Correct 13 ms 21520 KB Output is correct
3 Correct 11 ms 21460 KB Output is correct
4 Correct 11 ms 21588 KB Output is correct
5 Correct 11 ms 21588 KB Output is correct
6 Correct 11 ms 21588 KB Output is correct
7 Correct 12 ms 21524 KB Output is correct
8 Correct 12 ms 21588 KB Output is correct
9 Correct 12 ms 21592 KB Output is correct
10 Correct 10 ms 21556 KB Output is correct
11 Correct 11 ms 21588 KB Output is correct
12 Correct 10 ms 21588 KB Output is correct
13 Correct 10 ms 21588 KB Output is correct
14 Correct 10 ms 21588 KB Output is correct
15 Correct 14 ms 21544 KB Output is correct
16 Correct 10 ms 21588 KB Output is correct
17 Correct 10 ms 21588 KB Output is correct
18 Correct 12 ms 21588 KB Output is correct
19 Correct 11 ms 21588 KB Output is correct
20 Correct 11 ms 21644 KB Output is correct
21 Correct 12 ms 21588 KB Output is correct
22 Correct 9 ms 21588 KB Output is correct
23 Correct 10 ms 21588 KB Output is correct
24 Correct 10 ms 21588 KB Output is correct
25 Correct 11 ms 21640 KB Output is correct
26 Correct 10 ms 21588 KB Output is correct
27 Correct 10 ms 21480 KB Output is correct
28 Correct 12 ms 21484 KB Output is correct
29 Correct 11 ms 21460 KB Output is correct
30 Correct 14 ms 21844 KB Output is correct
31 Correct 14 ms 21944 KB Output is correct
32 Correct 16 ms 21972 KB Output is correct
33 Correct 16 ms 22060 KB Output is correct
34 Correct 15 ms 22068 KB Output is correct
35 Correct 12 ms 21972 KB Output is correct
36 Correct 12 ms 21972 KB Output is correct
37 Correct 12 ms 21972 KB Output is correct
38 Correct 17 ms 22012 KB Output is correct
39 Correct 15 ms 22108 KB Output is correct
40 Correct 15 ms 22108 KB Output is correct
41 Correct 12 ms 22080 KB Output is correct
42 Correct 12 ms 22100 KB Output is correct
43 Correct 13 ms 22024 KB Output is correct
44 Correct 18 ms 21972 KB Output is correct
45 Correct 16 ms 22052 KB Output is correct
46 Correct 15 ms 22084 KB Output is correct
47 Correct 14 ms 21972 KB Output is correct
48 Correct 12 ms 21972 KB Output is correct
49 Correct 13 ms 21936 KB Output is correct
50 Correct 15 ms 22008 KB Output is correct
51 Correct 16 ms 22024 KB Output is correct
52 Correct 15 ms 21972 KB Output is correct
53 Correct 14 ms 21972 KB Output is correct
54 Correct 17 ms 22076 KB Output is correct
55 Correct 14 ms 21972 KB Output is correct
56 Correct 11 ms 21588 KB Output is correct
57 Correct 11 ms 21712 KB Output is correct
58 Correct 13 ms 21716 KB Output is correct
59 Correct 10 ms 21560 KB Output is correct
60 Correct 10 ms 21460 KB Output is correct
61 Correct 10 ms 21588 KB Output is correct
62 Correct 255 ms 39836 KB Output is correct
63 Correct 184 ms 43424 KB Output is correct
64 Correct 259 ms 45832 KB Output is correct
65 Correct 324 ms 53328 KB Output is correct
66 Correct 329 ms 53304 KB Output is correct
67 Correct 324 ms 53324 KB Output is correct
68 Correct 330 ms 53432 KB Output is correct
69 Correct 332 ms 53484 KB Output is correct
70 Correct 108 ms 50148 KB Output is correct
71 Correct 90 ms 50116 KB Output is correct
72 Correct 91 ms 50132 KB Output is correct
73 Correct 72 ms 40432 KB Output is correct
74 Correct 83 ms 42044 KB Output is correct
75 Correct 64 ms 30464 KB Output is correct
76 Correct 11 ms 21460 KB Output is correct
77 Correct 353 ms 31884 KB Output is correct
78 Correct 598 ms 35052 KB Output is correct
79 Correct 412 ms 35380 KB Output is correct
80 Correct 119 ms 40932 KB Output is correct
81 Correct 194 ms 41676 KB Output is correct
82 Correct 268 ms 41896 KB Output is correct
83 Correct 374 ms 42064 KB Output is correct
84 Correct 439 ms 42036 KB Output is correct
85 Correct 588 ms 41980 KB Output is correct
86 Correct 670 ms 42092 KB Output is correct
87 Correct 785 ms 42332 KB Output is correct
88 Correct 816 ms 42964 KB Output is correct
89 Correct 831 ms 44636 KB Output is correct
90 Correct 92 ms 37636 KB Output is correct
91 Correct 528 ms 43220 KB Output is correct
92 Correct 539 ms 43200 KB Output is correct
93 Correct 565 ms 43292 KB Output is correct
94 Correct 105 ms 40644 KB Output is correct
95 Correct 129 ms 41100 KB Output is correct
96 Correct 161 ms 41620 KB Output is correct
97 Correct 212 ms 41752 KB Output is correct
98 Correct 250 ms 41732 KB Output is correct
99 Correct 310 ms 41704 KB Output is correct
100 Correct 377 ms 41712 KB Output is correct
101 Correct 437 ms 41836 KB Output is correct
102 Correct 540 ms 41716 KB Output is correct
103 Correct 610 ms 41776 KB Output is correct
104 Correct 681 ms 41900 KB Output is correct
105 Correct 755 ms 42232 KB Output is correct
106 Correct 789 ms 42740 KB Output is correct
107 Correct 916 ms 43860 KB Output is correct
108 Correct 923 ms 45076 KB Output is correct
109 Correct 77 ms 37532 KB Output is correct
110 Correct 11 ms 21456 KB Output is correct
111 Correct 10 ms 21540 KB Output is correct
112 Correct 11 ms 21688 KB Output is correct
113 Correct 419 ms 38664 KB Output is correct
114 Correct 433 ms 38604 KB Output is correct
115 Correct 515 ms 43668 KB Output is correct
116 Correct 535 ms 46272 KB Output is correct
117 Correct 535 ms 46180 KB Output is correct
118 Correct 549 ms 46164 KB Output is correct
119 Correct 539 ms 46088 KB Output is correct
120 Correct 559 ms 46180 KB Output is correct
121 Correct 546 ms 46216 KB Output is correct
122 Correct 589 ms 46160 KB Output is correct
123 Correct 53 ms 29016 KB Output is correct
124 Correct 550 ms 48264 KB Output is correct
125 Correct 427 ms 43844 KB Output is correct
126 Correct 624 ms 49036 KB Output is correct
127 Correct 723 ms 49192 KB Output is correct
128 Correct 653 ms 49044 KB Output is correct
129 Correct 617 ms 49044 KB Output is correct
130 Correct 629 ms 48956 KB Output is correct
131 Correct 450 ms 52560 KB Output is correct
132 Correct 437 ms 53172 KB Output is correct
133 Correct 452 ms 50936 KB Output is correct
134 Correct 578 ms 48960 KB Output is correct
135 Correct 599 ms 48708 KB Output is correct
136 Correct 579 ms 48788 KB Output is correct
137 Correct 460 ms 49204 KB Output is correct
138 Correct 459 ms 49116 KB Output is correct
139 Correct 446 ms 49096 KB Output is correct
140 Correct 454 ms 49116 KB Output is correct
141 Correct 453 ms 49080 KB Output is correct
142 Correct 467 ms 49076 KB Output is correct
143 Correct 68 ms 35744 KB Output is correct
144 Correct 76 ms 37528 KB Output is correct