oj.uz

Submission #484011

# Submission time Handle Problem Language Result Execution time Memory
484011 2021-11-01T21:13:51 Z urosk Birthday gift (IZhO18_treearray) C++14
100 / 100
 974 ms 104732 KB 
//https://oj.uz/problem/view/IZhO18_treearray
// __builtin_popcount(x) broj bitova
// __builtin_popcountll(x) long long
#include "bits/stdc++.h"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define rall(a) a.begin(),a.end(),greater<int>()
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define pi 3.14159265358979323846
#define here cerr<<"---------------------------\n"
#define ceri(a,l,r) {for(ll i = l;i<=r;i++) cerr<<a[i]<< " ";cerr<<endl;}
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

void setIO(string inoutname)
{
	freopen((inoutname+".in").c_str(),"r",stdin);
    	freopen((inoutname+".out").c_str(),"w",stdout);
}
#define mod 1
ll gcd(ll a, ll b)
{
   if(b==0) return a;
   if(a==0) return b;
   if(a>=b)  return gcd(a%b,b);
   return  gcd(a,b%a);
}
ll lcm(ll a,ll b){
   return (a/gcd(a,b))*b;
}
ll add(ll a,ll b){
	a+=b;
	a+=mod;
	if(a>=mod) a%=mod;
	return a;
}
ll mul(ll a,ll b){return(a*b)%mod;}
#define maxn 200005
#define lg 25
ll n,m,q;
vector<ll> g[maxn];
set<ll> v[maxn];
set<ll> w[maxn];
ll a[maxn];
ll b[maxn];
ll in[maxn];
ll out[maxn];
ll st[maxn][lg];
ll ti = 1;
void dfs(ll u,ll par){
    st[u][0] = par;
    in[u] = ti;
    ti++;
    for(ll s : g[u]){
        if(s==par) continue;
        dfs(s,u);
    }
    out[u] = ti;
    ti++;
}
bool in_t(ll v,ll u){return in[u]<=in[v]&&out[u]>=out[v];}
void init(){
    for(ll j = 1;j<lg;j++){
        for(ll i = 1;i<=n;i++) st[i][j] = st[st[i][j-1]][j-1];
    }
}
ll lca(ll u,ll v){
    if(in_t(v,u)) return u;
    if(in_t(u,v)) return v;
    for(ll j = lg-1;j>=0;j--){
        if(!in_t(v,st[u][j])) u = st[u][j];
    }
    return st[u][0];
}
void tc(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> m >> q;
    for(ll i = 1;i<=n-1;i++){
        ll x,y; cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    for(ll i = 1;i<=m;i++) cin >> a[i];
    dfs(1,1);
    init();
    for(ll i = 1;i<=m-1;i++){
        w[a[i]].insert(i);
        b[i] = lca(a[i],a[i+1]);
        v[b[i]].insert(i);
    }
    w[a[m]].insert(m);
    while(q--){
        ll tip;
        cin >> tip;
        if(tip==1){
            ll i,x; cin >> i >> x;
            w[a[i]].erase(w[a[i]].find(i));
            a[i] = x;
            w[a[i]].insert(i);
            if(i>1){
                v[b[i-1]].erase(v[b[i-1]].find(i-1));
                b[i-1] = lca(a[i-1],a[i]);
                v[b[i-1]].insert(i-1);
            }
            if(i<m){
                v[b[i]].erase(v[b[i]].find(i));
                b[i] = lca(a[i],a[i+1]);
                v[b[i]].insert(i);
            }
        }else{
            ll l,r,x;
            cin >> l >> r >> x;
            auto it = v[x].lower_bound(l);
            if(it!=v[x].end()&&*it<r){
                cout<<*it<< " "<<*it+1<<endl;
            }else if(!w[x].empty()){
                auto j = w[x].lower_bound(l);
                if(j!=w[x].end()&&*j<=r) cout<<*j<< " "<<*j<<endl;
                else cout<<-1<< " "<<-1<<endl;
            }else cout<<-1<< " "<<-1<<endl;
        }
    }
}
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
	//setIO("lol");
	int t; t = 1;
	while(t--){
		tc();
	}
	return 0;
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

Compilation message

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

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23756 KB n=5
2 Correct 12 ms 23792 KB n=100
3 Correct 13 ms 23804 KB n=100
4 Correct 11 ms 23776 KB n=100
5 Correct 10 ms 23756 KB n=100
6 Correct 11 ms 23800 KB n=100
7 Correct 12 ms 23796 KB n=100
8 Correct 11 ms 23756 KB n=100
9 Correct 11 ms 23828 KB n=100
10 Correct 13 ms 23868 KB n=100
11 Correct 11 ms 23808 KB n=100
12 Correct 10 ms 23804 KB n=100
13 Correct 12 ms 23804 KB n=100
14 Correct 10 ms 23756 KB n=100
15 Correct 10 ms 23756 KB n=100
16 Correct 11 ms 23756 KB n=100
17 Correct 11 ms 23800 KB n=100
18 Correct 11 ms 23756 KB n=100
19 Correct 11 ms 23804 KB n=100
20 Correct 11 ms 23756 KB n=100
21 Correct 10 ms 23756 KB n=100
22 Correct 10 ms 23756 KB n=100
23 Correct 11 ms 23756 KB n=100
24 Correct 11 ms 23804 KB n=100
25 Correct 11 ms 23752 KB n=100
26 Correct 11 ms 23756 KB n=12
27 Correct 10 ms 23752 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23756 KB n=5
2 Correct 12 ms 23792 KB n=100
3 Correct 13 ms 23804 KB n=100
4 Correct 11 ms 23776 KB n=100
5 Correct 10 ms 23756 KB n=100
6 Correct 11 ms 23800 KB n=100
7 Correct 12 ms 23796 KB n=100
8 Correct 11 ms 23756 KB n=100
9 Correct 11 ms 23828 KB n=100
10 Correct 13 ms 23868 KB n=100
11 Correct 11 ms 23808 KB n=100
12 Correct 10 ms 23804 KB n=100
13 Correct 12 ms 23804 KB n=100
14 Correct 10 ms 23756 KB n=100
15 Correct 10 ms 23756 KB n=100
16 Correct 11 ms 23756 KB n=100
17 Correct 11 ms 23800 KB n=100
18 Correct 11 ms 23756 KB n=100
19 Correct 11 ms 23804 KB n=100
20 Correct 11 ms 23756 KB n=100
21 Correct 10 ms 23756 KB n=100
22 Correct 10 ms 23756 KB n=100
23 Correct 11 ms 23756 KB n=100
24 Correct 11 ms 23804 KB n=100
25 Correct 11 ms 23752 KB n=100
26 Correct 11 ms 23756 KB n=12
27 Correct 10 ms 23752 KB n=100
28 Correct 11 ms 24012 KB n=500
29 Correct 12 ms 23936 KB n=500
30 Correct 11 ms 23948 KB n=500
31 Correct 11 ms 24012 KB n=500
32 Correct 12 ms 23976 KB n=500
33 Correct 12 ms 24012 KB n=500
34 Correct 12 ms 24012 KB n=500
35 Correct 11 ms 24012 KB n=500
36 Correct 11 ms 23996 KB n=500
37 Correct 13 ms 24004 KB n=500
38 Correct 12 ms 23940 KB n=500
39 Correct 12 ms 24012 KB n=500
40 Correct 11 ms 23944 KB n=500
41 Correct 11 ms 23992 KB n=500
42 Correct 11 ms 24012 KB n=500
43 Correct 11 ms 24012 KB n=500
44 Correct 13 ms 23908 KB n=500
45 Correct 11 ms 23980 KB n=500
46 Correct 11 ms 24048 KB n=500
47 Correct 11 ms 23964 KB n=500
48 Correct 11 ms 24012 KB n=500
49 Correct 12 ms 24012 KB n=500
50 Correct 14 ms 23940 KB n=500
51 Correct 12 ms 24004 KB n=500
52 Correct 14 ms 23936 KB n=500
53 Correct 13 ms 23948 KB n=500
54 Correct 11 ms 24012 KB n=500
55 Correct 13 ms 23884 KB n=278
56 Correct 11 ms 24032 KB n=500
57 Correct 11 ms 24012 KB n=500
58 Correct 11 ms 24012 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23756 KB n=5
2 Correct 12 ms 23792 KB n=100
3 Correct 13 ms 23804 KB n=100
4 Correct 11 ms 23776 KB n=100
5 Correct 10 ms 23756 KB n=100
6 Correct 11 ms 23800 KB n=100
7 Correct 12 ms 23796 KB n=100
8 Correct 11 ms 23756 KB n=100
9 Correct 11 ms 23828 KB n=100
10 Correct 13 ms 23868 KB n=100
11 Correct 11 ms 23808 KB n=100
12 Correct 10 ms 23804 KB n=100
13 Correct 12 ms 23804 KB n=100
14 Correct 10 ms 23756 KB n=100
15 Correct 10 ms 23756 KB n=100
16 Correct 11 ms 23756 KB n=100
17 Correct 11 ms 23800 KB n=100
18 Correct 11 ms 23756 KB n=100
19 Correct 11 ms 23804 KB n=100
20 Correct 11 ms 23756 KB n=100
21 Correct 10 ms 23756 KB n=100
22 Correct 10 ms 23756 KB n=100
23 Correct 11 ms 23756 KB n=100
24 Correct 11 ms 23804 KB n=100
25 Correct 11 ms 23752 KB n=100
26 Correct 11 ms 23756 KB n=12
27 Correct 10 ms 23752 KB n=100
28 Correct 11 ms 24012 KB n=500
29 Correct 12 ms 23936 KB n=500
30 Correct 11 ms 23948 KB n=500
31 Correct 11 ms 24012 KB n=500
32 Correct 12 ms 23976 KB n=500
33 Correct 12 ms 24012 KB n=500
34 Correct 12 ms 24012 KB n=500
35 Correct 11 ms 24012 KB n=500
36 Correct 11 ms 23996 KB n=500
37 Correct 13 ms 24004 KB n=500
38 Correct 12 ms 23940 KB n=500
39 Correct 12 ms 24012 KB n=500
40 Correct 11 ms 23944 KB n=500
41 Correct 11 ms 23992 KB n=500
42 Correct 11 ms 24012 KB n=500
43 Correct 11 ms 24012 KB n=500
44 Correct 13 ms 23908 KB n=500
45 Correct 11 ms 23980 KB n=500
46 Correct 11 ms 24048 KB n=500
47 Correct 11 ms 23964 KB n=500
48 Correct 11 ms 24012 KB n=500
49 Correct 12 ms 24012 KB n=500
50 Correct 14 ms 23940 KB n=500
51 Correct 12 ms 24004 KB n=500
52 Correct 14 ms 23936 KB n=500
53 Correct 13 ms 23948 KB n=500
54 Correct 11 ms 24012 KB n=500
55 Correct 13 ms 23884 KB n=278
56 Correct 11 ms 24032 KB n=500
57 Correct 11 ms 24012 KB n=500
58 Correct 11 ms 24012 KB n=500
59 Correct 14 ms 24600 KB n=2000
60 Correct 13 ms 24652 KB n=2000
61 Correct 13 ms 24624 KB n=2000
62 Correct 13 ms 24584 KB n=2000
63 Correct 13 ms 24584 KB n=2000
64 Correct 14 ms 24584 KB n=2000
65 Correct 14 ms 24584 KB n=2000
66 Correct 13 ms 24624 KB n=2000
67 Correct 14 ms 24524 KB n=2000
68 Correct 13 ms 24648 KB n=2000
69 Correct 13 ms 24524 KB n=2000
70 Correct 17 ms 24604 KB n=2000
71 Correct 17 ms 24524 KB n=2000
72 Correct 14 ms 24628 KB n=2000
73 Correct 13 ms 24524 KB n=2000
74 Correct 13 ms 24568 KB n=1844
75 Correct 13 ms 24524 KB n=2000
76 Correct 14 ms 24584 KB n=2000
77 Correct 14 ms 24580 KB n=2000
78 Correct 14 ms 24524 KB n=2000
79 Correct 19 ms 24588 KB n=2000
80 Correct 14 ms 24652 KB n=2000
81 Correct 19 ms 24580 KB n=2000
82 Correct 14 ms 24584 KB n=2000
83 Correct 13 ms 24584 KB n=2000
84 Correct 14 ms 24524 KB n=2000
85 Correct 14 ms 24648 KB n=2000
86 Correct 14 ms 24524 KB n=2000
87 Correct 13 ms 24600 KB n=2000
88 Correct 14 ms 24580 KB n=2000
89 Correct 17 ms 24572 KB n=2000
90 Correct 13 ms 24652 KB n=2000
91 Correct 14 ms 24524 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23756 KB n=5
2 Correct 12 ms 23792 KB n=100
3 Correct 13 ms 23804 KB n=100
4 Correct 11 ms 23776 KB n=100
5 Correct 10 ms 23756 KB n=100
6 Correct 11 ms 23800 KB n=100
7 Correct 12 ms 23796 KB n=100
8 Correct 11 ms 23756 KB n=100
9 Correct 11 ms 23828 KB n=100
10 Correct 13 ms 23868 KB n=100
11 Correct 11 ms 23808 KB n=100
12 Correct 10 ms 23804 KB n=100
13 Correct 12 ms 23804 KB n=100
14 Correct 10 ms 23756 KB n=100
15 Correct 10 ms 23756 KB n=100
16 Correct 11 ms 23756 KB n=100
17 Correct 11 ms 23800 KB n=100
18 Correct 11 ms 23756 KB n=100
19 Correct 11 ms 23804 KB n=100
20 Correct 11 ms 23756 KB n=100
21 Correct 10 ms 23756 KB n=100
22 Correct 10 ms 23756 KB n=100
23 Correct 11 ms 23756 KB n=100
24 Correct 11 ms 23804 KB n=100
25 Correct 11 ms 23752 KB n=100
26 Correct 11 ms 23756 KB n=12
27 Correct 10 ms 23752 KB n=100
28 Correct 11 ms 24012 KB n=500
29 Correct 12 ms 23936 KB n=500
30 Correct 11 ms 23948 KB n=500
31 Correct 11 ms 24012 KB n=500
32 Correct 12 ms 23976 KB n=500
33 Correct 12 ms 24012 KB n=500
34 Correct 12 ms 24012 KB n=500
35 Correct 11 ms 24012 KB n=500
36 Correct 11 ms 23996 KB n=500
37 Correct 13 ms 24004 KB n=500
38 Correct 12 ms 23940 KB n=500
39 Correct 12 ms 24012 KB n=500
40 Correct 11 ms 23944 KB n=500
41 Correct 11 ms 23992 KB n=500
42 Correct 11 ms 24012 KB n=500
43 Correct 11 ms 24012 KB n=500
44 Correct 13 ms 23908 KB n=500
45 Correct 11 ms 23980 KB n=500
46 Correct 11 ms 24048 KB n=500
47 Correct 11 ms 23964 KB n=500
48 Correct 11 ms 24012 KB n=500
49 Correct 12 ms 24012 KB n=500
50 Correct 14 ms 23940 KB n=500
51 Correct 12 ms 24004 KB n=500
52 Correct 14 ms 23936 KB n=500
53 Correct 13 ms 23948 KB n=500
54 Correct 11 ms 24012 KB n=500
55 Correct 13 ms 23884 KB n=278
56 Correct 11 ms 24032 KB n=500
57 Correct 11 ms 24012 KB n=500
58 Correct 11 ms 24012 KB n=500
59 Correct 14 ms 24600 KB n=2000
60 Correct 13 ms 24652 KB n=2000
61 Correct 13 ms 24624 KB n=2000
62 Correct 13 ms 24584 KB n=2000
63 Correct 13 ms 24584 KB n=2000
64 Correct 14 ms 24584 KB n=2000
65 Correct 14 ms 24584 KB n=2000
66 Correct 13 ms 24624 KB n=2000
67 Correct 14 ms 24524 KB n=2000
68 Correct 13 ms 24648 KB n=2000
69 Correct 13 ms 24524 KB n=2000
70 Correct 17 ms 24604 KB n=2000
71 Correct 17 ms 24524 KB n=2000
72 Correct 14 ms 24628 KB n=2000
73 Correct 13 ms 24524 KB n=2000
74 Correct 13 ms 24568 KB n=1844
75 Correct 13 ms 24524 KB n=2000
76 Correct 14 ms 24584 KB n=2000
77 Correct 14 ms 24580 KB n=2000
78 Correct 14 ms 24524 KB n=2000
79 Correct 19 ms 24588 KB n=2000
80 Correct 14 ms 24652 KB n=2000
81 Correct 19 ms 24580 KB n=2000
82 Correct 14 ms 24584 KB n=2000
83 Correct 13 ms 24584 KB n=2000
84 Correct 14 ms 24524 KB n=2000
85 Correct 14 ms 24648 KB n=2000
86 Correct 14 ms 24524 KB n=2000
87 Correct 13 ms 24600 KB n=2000
88 Correct 14 ms 24580 KB n=2000
89 Correct 17 ms 24572 KB n=2000
90 Correct 13 ms 24652 KB n=2000
91 Correct 14 ms 24524 KB n=2000
92 Correct 722 ms 97324 KB n=200000
93 Correct 783 ms 100972 KB n=200000
94 Correct 575 ms 103876 KB n=200000
95 Correct 684 ms 97052 KB n=200000
96 Correct 692 ms 97116 KB n=200000
97 Correct 831 ms 100072 KB n=200000
98 Correct 678 ms 97140 KB n=200000
99 Correct 875 ms 96752 KB n=200000
100 Correct 758 ms 97244 KB n=200000
101 Correct 515 ms 104732 KB n=200000
102 Correct 433 ms 98328 KB n=200000
103 Correct 423 ms 98256 KB n=200000
104 Correct 461 ms 98280 KB n=200000
105 Correct 456 ms 97892 KB n=200000
106 Correct 462 ms 97964 KB n=200000
107 Correct 446 ms 97828 KB n=200000
108 Correct 782 ms 96820 KB n=200000
109 Correct 716 ms 96852 KB n=200000
110 Correct 729 ms 96872 KB n=200000
111 Correct 700 ms 96948 KB n=200000
112 Correct 540 ms 103912 KB n=200000
113 Correct 787 ms 99892 KB n=200000
114 Correct 712 ms 96956 KB n=200000
115 Correct 974 ms 97844 KB n=200000
116 Correct 633 ms 96776 KB n=200000
117 Correct 523 ms 104112 KB n=200000
118 Correct 863 ms 98756 KB n=200000
119 Correct 616 ms 96816 KB n=200000
120 Correct 467 ms 104264 KB n=200000
121 Correct 459 ms 104212 KB n=200000
122 Correct 456 ms 104692 KB n=200000
123 Correct 440 ms 97476 KB n=200000
124 Correct 144 ms 41176 KB n=25264