oj.uz

Submission #963361

# Submission time Handle Problem Language Result Execution time Memory
963361 2024-04-14T21:38:07 Z MarwenElarbi Tourism (JOI23_tourism) C++17
100 / 100
 1220 ms 21792 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define vi vector<int>
#define ve vector
#define ll long long
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define onbit __builtin_popcount
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e18
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
using namespace std;
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll MOD = 1e9+7;
const int nax = 1e5+5;
const int MAX_VAL = 1e6+1;
double PI=3.14159265359;
int arx[8]={1,0,0,-1,-1,-1, 1, 1};
int ary[8]={0,1,-1, 0, 1,-1,-1, 1};
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
struct Query{
    int l,r,idx;
};
int n,m;
vi adj[nax];
int c[nax];
vector<Query> queries;
int sz[nax], p[nax], dep[nax];
int segtree[nax*4], id[nax], tp[nax];
int nxt[nax];
int val[nax];
set<int> intervals;
bool cmp(Query x,Query y){
    if(x.r!=y.r) return x.r<y.r;
    else return x.l<y.l;
}
//segtree
void update(int pos,int l,int r,int idx,int value){
    if(l==r){
        segtree[pos]+=value;
        return;
    }
    int mid=(r+l)/2;
    if(idx<=mid) update(pos*2+1,l,mid,idx,value);
    else update(pos*2+2,mid+1,r,idx,value);
    segtree[pos]=segtree[pos*2+1]+segtree[pos*2+2];
    return;
}
int query(int pos,int l,int r,int left,int right){
    if(l>r||l>right||r<left) return 0;
    if(l>=left&&r<=right) return segtree[pos];
    int mid=(r+l)/2;
    //cout <<l<<" "<<r<<endl;
    return query(pos*2+1,l,mid,left,right)+query(pos*2+2,mid+1,r,left,right);
}
//HLD
int dfs_sz(int cur, int par) {
    sz[cur] = 1;
    p[cur] = par;
    for (int chi : adj[cur]) {
        if (chi == par) continue;
        dep[chi] = dep[cur] + 1;
        p[chi] = cur;
        sz[cur] += dfs_sz(chi, cur);
    }
    return sz[cur];
}

int ct = 1;

void dfs_hld(int cur, int par, int top) {
    id[cur] = ct++;
    tp[cur] = top;
    nxt[cur]=id[top];
    //update(id[cur], v[cur]);
    int h_chi = -1, h_sz = -1;
    for (int chi : adj[cur]) {
        if (chi == par) continue;
        if (sz[chi] > h_sz) {
            h_sz = sz[chi];
            h_chi = chi;
        }
    }
    if (h_chi == -1) return;
    dfs_hld(h_chi, cur, top);
    for (int chi : adj[cur]) {
        if (chi == par || chi == h_chi) continue;
        dfs_hld(chi, cur, chi);
    }
}
void updateAns(int l, int r, int x) {
    //cout <<l<<" "<<r<<" "<<x<<endl;
    set<int>::iterator it;
    it = intervals.lower_bound(l);
    if (it != intervals.begin()) it--;
    vector<int> to_rem;
    vector<int> to_add;
    while (it != intervals.end()) {
        int a = *it;
        int b = nxt[a];
        if (a > r) break;
        if (a < l && b < l) {
            it++;
            continue;
        }
        if (a < l) {
            update(0,0,m+2,val[a], -(b - a + 1));
            nxt[a] = l - 1;
            update(0,0,m+2,val[a], (nxt[a] - a + 1));
        } else {
            update(0,0,m+2,val[a], -(b - a + 1));
            to_rem.pb(a);
        }
        if (b > r) {
            to_add.pb(r + 1);
            val[r+1]=val[a];
            update(0,0,m+2,val[a], b - r);
            nxt[r + 1] = b;
        }
        it++;
    }
    //cout <<segtree[0]<<endl;
    nxt[l] = r;
    val[l] = x;
    update(0,0,m+2,x, r - l + 1);
    //cout <<segtree[0]<<endl;
    for (auto &u : to_rem) {
        assert(intervals.count(u));
        intervals.erase(u);
    }
    for (auto &u : to_add) {
        intervals.insert(u);
    }
    intervals.insert(l);
}
void path(int x, int y,int value) {
    while (tp[x] != tp[y]) {
        if (dep[tp[x]] < dep[tp[y]]) swap(x, y);
        updateAns(id[tp[x]], id[x], value);
        x = p[tp[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    updateAns(id[x], id[y], value);
    return;
}

int main(){
    optimise;
    //setIO("dec");
    int q;
    cin>>n>>m>>q;
    for (int i = 0; i < n-1; ++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    for (int i = 0; i < m; ++i)
    {
        cin>>c[i];
        c[i]--;
    }
    dfs_sz(0,-1);
    dfs_hld(0,-1,0);
    for (int i = 0; i < q; ++i)
    {
        queries.emplace_back();
        cin>>queries[i].l>>queries[i].r;
        queries[i].idx=i;
        queries[i].l--;
        queries[i].r--;
    }
    //return 0;
    //cout <<"nabba"<<endl;
    sort(queries.begin(),queries.end(),cmp);
    int j=0;
    int ans[q];
    for (int i = 0; i < m; ++i)
    {
        //cout <<queries[j].l<<" "<<queries[j].r<<" "<<queries[j].idx<<endl;
        if(i){
            path(c[i-1],c[i],i);
            //cout <<"nab"<<endl;
        }path(c[i],c[i],i+1);
        while(j<q&&queries[j].r==i){
            ans[queries[j].idx]=query(0,0,m+2,queries[j].l+1,m+1);
            //cout <<"kalil"<<endl;
            j++;
        }
        
    }
    for (int i = 0; i < q; ++i)
    {
        cout <<ans[i]<<endl;
    }
}

Compilation message

tourism.cpp: In function 'void setIO(std::string)':
tourism.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 1 ms 7256 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 3 ms 7344 KB Output is correct
10 Correct 3 ms 7256 KB Output is correct
11 Correct 3 ms 7348 KB Output is correct
12 Correct 3 ms 7344 KB Output is correct
13 Correct 2 ms 7260 KB Output is correct
14 Correct 3 ms 7260 KB Output is correct
15 Correct 3 ms 7260 KB Output is correct
16 Correct 3 ms 7260 KB Output is correct
17 Correct 3 ms 7260 KB Output is correct
18 Correct 3 ms 7260 KB Output is correct
19 Correct 3 ms 7260 KB Output is correct
20 Correct 2 ms 7596 KB Output is correct
21 Correct 2 ms 7364 KB Output is correct
22 Correct 2 ms 7260 KB Output is correct
23 Correct 2 ms 7260 KB Output is correct
24 Correct 3 ms 7260 KB Output is correct
25 Correct 2 ms 7260 KB Output is correct
26 Correct 3 ms 7260 KB Output is correct
27 Correct 2 ms 7260 KB Output is correct
28 Correct 2 ms 7340 KB Output is correct
29 Correct 3 ms 7260 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 1 ms 7256 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 3 ms 7344 KB Output is correct
10 Correct 3 ms 7256 KB Output is correct
11 Correct 3 ms 7348 KB Output is correct
12 Correct 3 ms 7344 KB Output is correct
13 Correct 2 ms 7260 KB Output is correct
14 Correct 3 ms 7260 KB Output is correct
15 Correct 3 ms 7260 KB Output is correct
16 Correct 3 ms 7260 KB Output is correct
17 Correct 3 ms 7260 KB Output is correct
18 Correct 3 ms 7260 KB Output is correct
19 Correct 3 ms 7260 KB Output is correct
20 Correct 2 ms 7596 KB Output is correct
21 Correct 2 ms 7364 KB Output is correct
22 Correct 2 ms 7260 KB Output is correct
23 Correct 2 ms 7260 KB Output is correct
24 Correct 3 ms 7260 KB Output is correct
25 Correct 2 ms 7260 KB Output is correct
26 Correct 3 ms 7260 KB Output is correct
27 Correct 2 ms 7260 KB Output is correct
28 Correct 2 ms 7340 KB Output is correct
29 Correct 3 ms 7260 KB Output is correct
30 Correct 8 ms 7488 KB Output is correct
31 Correct 11 ms 7632 KB Output is correct
32 Correct 11 ms 7512 KB Output is correct
33 Correct 10 ms 7512 KB Output is correct
34 Correct 13 ms 7540 KB Output is correct
35 Correct 13 ms 7512 KB Output is correct
36 Correct 11 ms 7516 KB Output is correct
37 Correct 11 ms 7540 KB Output is correct
38 Correct 7 ms 7516 KB Output is correct
39 Correct 7 ms 7516 KB Output is correct
40 Correct 7 ms 7516 KB Output is correct
41 Correct 7 ms 7516 KB Output is correct
42 Correct 7 ms 7440 KB Output is correct
43 Correct 7 ms 7512 KB Output is correct
44 Correct 8 ms 7556 KB Output is correct
45 Correct 8 ms 7516 KB Output is correct
46 Correct 8 ms 7512 KB Output is correct
47 Correct 8 ms 7352 KB Output is correct
48 Correct 12 ms 7520 KB Output is correct
49 Correct 11 ms 7516 KB Output is correct
50 Correct 7 ms 7572 KB Output is correct
51 Correct 10 ms 5640 KB Output is correct
52 Correct 7 ms 5468 KB Output is correct
53 Correct 7 ms 5464 KB Output is correct
54 Correct 7 ms 5464 KB Output is correct
55 Correct 7 ms 5520 KB Output is correct
56 Correct 5 ms 5296 KB Output is correct
57 Correct 5 ms 5488 KB Output is correct
58 Correct 11 ms 5300 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 4 ms 3164 KB Output is correct
4 Correct 226 ms 15300 KB Output is correct
5 Correct 183 ms 17880 KB Output is correct
6 Correct 208 ms 19120 KB Output is correct
7 Correct 286 ms 21528 KB Output is correct
8 Correct 290 ms 21644 KB Output is correct
9 Correct 303 ms 21668 KB Output is correct
10 Correct 313 ms 21792 KB Output is correct
11 Correct 319 ms 21576 KB Output is correct
12 Correct 296 ms 21704 KB Output is correct
13 Correct 299 ms 21648 KB Output is correct
14 Correct 289 ms 21640 KB Output is correct
15 Correct 151 ms 19916 KB Output is correct
16 Correct 280 ms 21204 KB Output is correct
17 Correct 191 ms 10496 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7336 KB Output is correct
2 Correct 308 ms 11680 KB Output is correct
3 Correct 575 ms 12124 KB Output is correct
4 Correct 404 ms 12624 KB Output is correct
5 Correct 624 ms 14772 KB Output is correct
6 Correct 643 ms 14928 KB Output is correct
7 Correct 683 ms 15008 KB Output is correct
8 Correct 666 ms 14956 KB Output is correct
9 Correct 650 ms 14956 KB Output is correct
10 Correct 710 ms 14868 KB Output is correct
11 Correct 621 ms 14932 KB Output is correct
12 Correct 634 ms 14928 KB Output is correct
13 Correct 688 ms 14660 KB Output is correct
14 Correct 731 ms 15740 KB Output is correct
15 Correct 775 ms 17416 KB Output is correct
16 Correct 634 ms 14744 KB Output is correct
17 Correct 692 ms 14740 KB Output is correct
18 Correct 654 ms 14576 KB Output is correct
19 Correct 447 ms 12136 KB Output is correct
20 Correct 445 ms 12176 KB Output is correct
21 Correct 464 ms 11948 KB Output is correct
22 Correct 468 ms 12068 KB Output is correct
23 Correct 443 ms 11872 KB Output is correct
24 Correct 457 ms 12092 KB Output is correct
25 Correct 457 ms 11972 KB Output is correct
26 Correct 443 ms 12140 KB Output is correct
27 Correct 431 ms 11996 KB Output is correct
28 Correct 452 ms 12212 KB Output is correct
29 Correct 447 ms 11928 KB Output is correct
30 Correct 490 ms 12168 KB Output is correct
31 Correct 463 ms 12572 KB Output is correct
32 Correct 470 ms 12584 KB Output is correct
33 Correct 528 ms 13388 KB Output is correct
34 Correct 584 ms 15204 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2816 KB Output is correct
2 Correct 2 ms 2648 KB Output is correct
3 Correct 7 ms 2824 KB Output is correct
4 Correct 963 ms 13516 KB Output is correct
5 Correct 986 ms 13788 KB Output is correct
6 Correct 1087 ms 16392 KB Output is correct
7 Correct 1178 ms 17820 KB Output is correct
8 Correct 1220 ms 17784 KB Output is correct
9 Correct 1124 ms 17960 KB Output is correct
10 Correct 1161 ms 17976 KB Output is correct
11 Correct 1149 ms 17876 KB Output is correct
12 Correct 1155 ms 17984 KB Output is correct
13 Correct 1166 ms 18372 KB Output is correct
14 Correct 195 ms 10436 KB Output is correct

Subtask #6
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 1 ms 7256 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 3 ms 7344 KB Output is correct
10 Correct 3 ms 7256 KB Output is correct
11 Correct 3 ms 7348 KB Output is correct
12 Correct 3 ms 7344 KB Output is correct
13 Correct 2 ms 7260 KB Output is correct
14 Correct 3 ms 7260 KB Output is correct
15 Correct 3 ms 7260 KB Output is correct
16 Correct 3 ms 7260 KB Output is correct
17 Correct 3 ms 7260 KB Output is correct
18 Correct 3 ms 7260 KB Output is correct
19 Correct 3 ms 7260 KB Output is correct
20 Correct 2 ms 7596 KB Output is correct
21 Correct 2 ms 7364 KB Output is correct
22 Correct 2 ms 7260 KB Output is correct
23 Correct 2 ms 7260 KB Output is correct
24 Correct 3 ms 7260 KB Output is correct
25 Correct 2 ms 7260 KB Output is correct
26 Correct 3 ms 7260 KB Output is correct
27 Correct 2 ms 7260 KB Output is correct
28 Correct 2 ms 7340 KB Output is correct
29 Correct 3 ms 7260 KB Output is correct
30 Correct 8 ms 7488 KB Output is correct
31 Correct 11 ms 7632 KB Output is correct
32 Correct 11 ms 7512 KB Output is correct
33 Correct 10 ms 7512 KB Output is correct
34 Correct 13 ms 7540 KB Output is correct
35 Correct 13 ms 7512 KB Output is correct
36 Correct 11 ms 7516 KB Output is correct
37 Correct 11 ms 7540 KB Output is correct
38 Correct 7 ms 7516 KB Output is correct
39 Correct 7 ms 7516 KB Output is correct
40 Correct 7 ms 7516 KB Output is correct
41 Correct 7 ms 7516 KB Output is correct
42 Correct 7 ms 7440 KB Output is correct
43 Correct 7 ms 7512 KB Output is correct
44 Correct 8 ms 7556 KB Output is correct
45 Correct 8 ms 7516 KB Output is correct
46 Correct 8 ms 7512 KB Output is correct
47 Correct 8 ms 7352 KB Output is correct
48 Correct 12 ms 7520 KB Output is correct
49 Correct 11 ms 7516 KB Output is correct
50 Correct 7 ms 7572 KB Output is correct
51 Correct 10 ms 5640 KB Output is correct
52 Correct 7 ms 5468 KB Output is correct
53 Correct 7 ms 5464 KB Output is correct
54 Correct 7 ms 5464 KB Output is correct
55 Correct 7 ms 5520 KB Output is correct
56 Correct 5 ms 5296 KB Output is correct
57 Correct 5 ms 5488 KB Output is correct
58 Correct 11 ms 5300 KB Output is correct
59 Correct 1 ms 5208 KB Output is correct
60 Correct 2 ms 5212 KB Output is correct
61 Correct 4 ms 3164 KB Output is correct
62 Correct 226 ms 15300 KB Output is correct
63 Correct 183 ms 17880 KB Output is correct
64 Correct 208 ms 19120 KB Output is correct
65 Correct 286 ms 21528 KB Output is correct
66 Correct 290 ms 21644 KB Output is correct
67 Correct 303 ms 21668 KB Output is correct
68 Correct 313 ms 21792 KB Output is correct
69 Correct 319 ms 21576 KB Output is correct
70 Correct 296 ms 21704 KB Output is correct
71 Correct 299 ms 21648 KB Output is correct
72 Correct 289 ms 21640 KB Output is correct
73 Correct 151 ms 19916 KB Output is correct
74 Correct 280 ms 21204 KB Output is correct
75 Correct 191 ms 10496 KB Output is correct
76 Correct 2 ms 7336 KB Output is correct
77 Correct 308 ms 11680 KB Output is correct
78 Correct 575 ms 12124 KB Output is correct
79 Correct 404 ms 12624 KB Output is correct
80 Correct 624 ms 14772 KB Output is correct
81 Correct 643 ms 14928 KB Output is correct
82 Correct 683 ms 15008 KB Output is correct
83 Correct 666 ms 14956 KB Output is correct
84 Correct 650 ms 14956 KB Output is correct
85 Correct 710 ms 14868 KB Output is correct
86 Correct 621 ms 14932 KB Output is correct
87 Correct 634 ms 14928 KB Output is correct
88 Correct 688 ms 14660 KB Output is correct
89 Correct 731 ms 15740 KB Output is correct
90 Correct 775 ms 17416 KB Output is correct
91 Correct 634 ms 14744 KB Output is correct
92 Correct 692 ms 14740 KB Output is correct
93 Correct 654 ms 14576 KB Output is correct
94 Correct 447 ms 12136 KB Output is correct
95 Correct 445 ms 12176 KB Output is correct
96 Correct 464 ms 11948 KB Output is correct
97 Correct 468 ms 12068 KB Output is correct
98 Correct 443 ms 11872 KB Output is correct
99 Correct 457 ms 12092 KB Output is correct
100 Correct 457 ms 11972 KB Output is correct
101 Correct 443 ms 12140 KB Output is correct
102 Correct 431 ms 11996 KB Output is correct
103 Correct 452 ms 12212 KB Output is correct
104 Correct 447 ms 11928 KB Output is correct
105 Correct 490 ms 12168 KB Output is correct
106 Correct 463 ms 12572 KB Output is correct
107 Correct 470 ms 12584 KB Output is correct
108 Correct 528 ms 13388 KB Output is correct
109 Correct 584 ms 15204 KB Output is correct
110 Correct 1 ms 2816 KB Output is correct
111 Correct 2 ms 2648 KB Output is correct
112 Correct 7 ms 2824 KB Output is correct
113 Correct 963 ms 13516 KB Output is correct
114 Correct 986 ms 13788 KB Output is correct
115 Correct 1087 ms 16392 KB Output is correct
116 Correct 1178 ms 17820 KB Output is correct
117 Correct 1220 ms 17784 KB Output is correct
118 Correct 1124 ms 17960 KB Output is correct
119 Correct 1161 ms 17976 KB Output is correct
120 Correct 1149 ms 17876 KB Output is correct
121 Correct 1155 ms 17984 KB Output is correct
122 Correct 1166 ms 18372 KB Output is correct
123 Correct 195 ms 10436 KB Output is correct
124 Correct 652 ms 18004 KB Output is correct
125 Correct 513 ms 15904 KB Output is correct
126 Correct 854 ms 18396 KB Output is correct
127 Correct 844 ms 18212 KB Output is correct
128 Correct 792 ms 18244 KB Output is correct
129 Correct 800 ms 18188 KB Output is correct
130 Correct 852 ms 18236 KB Output is correct
131 Correct 323 ms 20676 KB Output is correct
132 Correct 315 ms 21488 KB Output is correct
133 Correct 309 ms 18656 KB Output is correct
134 Correct 643 ms 15644 KB Output is correct
135 Correct 618 ms 15764 KB Output is correct
136 Correct 633 ms 15820 KB Output is correct
137 Correct 389 ms 18908 KB Output is correct
138 Correct 361 ms 18780 KB Output is correct
139 Correct 359 ms 18900 KB Output is correct
140 Correct 353 ms 18936 KB Output is correct
141 Correct 370 ms 18924 KB Output is correct
142 Correct 372 ms 19124 KB Output is correct
143 Correct 179 ms 13768 KB Output is correct
144 Correct 795 ms 17880 KB Output is correct