oj.uz

Submission #863648

# Submission time Handle Problem Language Result Execution time Memory
863648 2023-10-20T16:31:58 Z nnhzzz Birthday gift (IZhO18_treearray) C++14
100 / 100
 795 ms 89412 KB 
// cre: Nguyen Ngoc Hung - Train VOI 2024

#include<bits/stdc++.h>

using namespace std;

#define        __nnhzzz__  signed main()
#define          BIT(i,j)  ((i>>j)&1LL)
#define           MASK(i)  (1LL<<i)
#define            ALL(x)  (x).begin(),(x).end()
#define             SZ(x)  (int)(x).size()
#define               gcd  __gcd
#define                fi  first
#define                se  second
#define                ll  long long
#define               ull  unsigned long long
#define                ld  long double
#define                vi  vector<int>
#define               vvi  vector<vi>
#define              vvvi  vector<vvi>
#define               pii  pair<int,int>
#define              vpii  vector<pii>
#define        REP(i,a,b)  for(int i = (a); i<=(b); ++i)
#define       REPD(i,a,b)  for(int i = (a); i>=(b); --i)
#define   REPDIS(i,a,b,c)  for(int i = (a); i<=(b); i+=c)
#define              endl  "\n"
// #define               int  ll

//-------------------------------------------------------------//
const int oo = 1e9,LOG = 18,MAXN = 2e5+7,N = 1e2+3;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
//-------------------------------------------------------------//
template<typename T> bool mini(T &a, const T &b){if(a>b){a=b;return true;}return false;}
template<typename T> bool maxi(T &a, const T &b){if(a<b){a=b;return true;}return false;}

/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Nguyen Ngoc Hung - nnhzzz
    Training for VOI24 gold medal
----------------------------------------------------------------
*/

int a[MAXN],b[MAXN],dep[MAXN],f[MAXN][LOG];
set<int> s1[MAXN],s2[MAXN];
vi adj[MAXN];

void dfs(int u, int par){
    REP(i,1,LOG-1) f[u][i] = f[f[u][i-1]][i-1];
    for(auto v:adj[u]){
        if(v==par) continue;
        f[v][0] = u;
        dep[v] = dep[u]+1;
        dfs(v,u);
    }
}

int lca(int u, int v){
    if(dep[u]>dep[v]) swap(u,v);
    int dis = dep[v]-dep[u];
    REPD(i,LOG-1,0){
        if(BIT(dis,i)){
            v = f[v][i];
        }
    }
    if(u==v) return u;
    REPD(i,LOG-1,0){
        if(f[u][i]!=f[v][i]){
            u = f[u][i];
            v = f[v][i];
        }
    }
    return f[u][0];
}

void ans(int i, int j){
    cout << i << " " << j << "\n";
}

void solve(){
    int n,m,q; cin >> n >> m >> q;
    REP(i,2,n){
        int u,v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0);
    REP(i,1,m){
        cin >> a[i];
        s2[a[i]].insert(i);
    }
    REP(i,1,m-1){
        b[i] = lca(a[i],a[i+1]);
        s1[b[i]].insert(i);
    }
    while(q--){
        int t; cin >> t;
        if(t==1){
            int pos,val; cin >> pos >> val;
            s2[a[pos]].erase(pos);
            if(pos<m){
                int x = lca(val,a[pos+1]);
                s1[b[pos]].erase(pos);
                b[pos] = x;
                s1[b[pos]].insert(pos);
            }
            if(pos>1){
                int x = lca(a[pos-1],val);
                s1[b[pos-1]].erase(pos-1);
                b[pos-1] = x;
                s1[b[pos-1]].insert(pos-1);
            }
            a[pos] = val;
            s2[a[pos]].insert(pos);
        }else{
            int l,r,x; cin >> l >> r >> x;
            if(l==r){
                if(a[l]==x) ans(l,l);
                else ans(-1,-1);
                continue;
            }
            auto it = s1[x].lower_bound(l);
            if(it!=s1[x].end() && *it<r){
                ans(*it,*it+1);
                continue;
            }
            auto it1 = s2[x].lower_bound(l);
            // cout << "waring: " << x << " ";
            if(it1!=s2[x].end() && *it1<=r) ans(*it1,*it1);
            else ans(-1,-1);
        }
    }
}

__nnhzzz__{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define name "test"
    if(fopen(name".inp","r")){
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    #define name1 "nnhzzz"
    if(fopen(name1".inp","r")){
        freopen(name1".inp","r",stdin);
        freopen(name1".out","w",stdout);
    }
    int test = 1;
    while(test--){
        solve();
    }
    cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         freopen(name1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         freopen(name1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25188 KB n=5
2 Correct 5 ms 25180 KB n=100
3 Correct 5 ms 25176 KB n=100
4 Correct 5 ms 25180 KB n=100
5 Correct 5 ms 25180 KB n=100
6 Correct 5 ms 25252 KB n=100
7 Correct 5 ms 25180 KB n=100
8 Correct 5 ms 25180 KB n=100
9 Correct 5 ms 25180 KB n=100
10 Correct 5 ms 25256 KB n=100
11 Correct 5 ms 25180 KB n=100
12 Correct 5 ms 25180 KB n=100
13 Correct 5 ms 25180 KB n=100
14 Correct 5 ms 25180 KB n=100
15 Correct 5 ms 25176 KB n=100
16 Correct 5 ms 25180 KB n=100
17 Correct 5 ms 25180 KB n=100
18 Correct 5 ms 25180 KB n=100
19 Correct 6 ms 25180 KB n=100
20 Correct 6 ms 25180 KB n=100
21 Correct 5 ms 25256 KB n=100
22 Correct 5 ms 25180 KB n=100
23 Correct 5 ms 25180 KB n=100
24 Correct 6 ms 25048 KB n=100
25 Correct 6 ms 25180 KB n=100
26 Correct 6 ms 25180 KB n=12
27 Correct 5 ms 25180 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25188 KB n=5
2 Correct 5 ms 25180 KB n=100
3 Correct 5 ms 25176 KB n=100
4 Correct 5 ms 25180 KB n=100
5 Correct 5 ms 25180 KB n=100
6 Correct 5 ms 25252 KB n=100
7 Correct 5 ms 25180 KB n=100
8 Correct 5 ms 25180 KB n=100
9 Correct 5 ms 25180 KB n=100
10 Correct 5 ms 25256 KB n=100
11 Correct 5 ms 25180 KB n=100
12 Correct 5 ms 25180 KB n=100
13 Correct 5 ms 25180 KB n=100
14 Correct 5 ms 25180 KB n=100
15 Correct 5 ms 25176 KB n=100
16 Correct 5 ms 25180 KB n=100
17 Correct 5 ms 25180 KB n=100
18 Correct 5 ms 25180 KB n=100
19 Correct 6 ms 25180 KB n=100
20 Correct 6 ms 25180 KB n=100
21 Correct 5 ms 25256 KB n=100
22 Correct 5 ms 25180 KB n=100
23 Correct 5 ms 25180 KB n=100
24 Correct 6 ms 25048 KB n=100
25 Correct 6 ms 25180 KB n=100
26 Correct 6 ms 25180 KB n=12
27 Correct 5 ms 25180 KB n=100
28 Correct 8 ms 25180 KB n=500
29 Correct 7 ms 25180 KB n=500
30 Correct 7 ms 25176 KB n=500
31 Correct 7 ms 25180 KB n=500
32 Correct 8 ms 25180 KB n=500
33 Correct 7 ms 25180 KB n=500
34 Correct 7 ms 25180 KB n=500
35 Correct 7 ms 25180 KB n=500
36 Correct 7 ms 25180 KB n=500
37 Correct 7 ms 25176 KB n=500
38 Correct 6 ms 25176 KB n=500
39 Correct 7 ms 25432 KB n=500
40 Correct 6 ms 25180 KB n=500
41 Correct 7 ms 25180 KB n=500
42 Correct 7 ms 25176 KB n=500
43 Correct 6 ms 25180 KB n=500
44 Correct 6 ms 25176 KB n=500
45 Correct 6 ms 25180 KB n=500
46 Correct 6 ms 25180 KB n=500
47 Correct 6 ms 25180 KB n=500
48 Correct 7 ms 25180 KB n=500
49 Correct 8 ms 25180 KB n=500
50 Correct 6 ms 25180 KB n=500
51 Correct 6 ms 25180 KB n=500
52 Correct 6 ms 25180 KB n=500
53 Correct 6 ms 25176 KB n=500
54 Correct 7 ms 25180 KB n=500
55 Correct 5 ms 25180 KB n=278
56 Correct 6 ms 25176 KB n=500
57 Correct 6 ms 25176 KB n=500
58 Correct 6 ms 25180 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25188 KB n=5
2 Correct 5 ms 25180 KB n=100
3 Correct 5 ms 25176 KB n=100
4 Correct 5 ms 25180 KB n=100
5 Correct 5 ms 25180 KB n=100
6 Correct 5 ms 25252 KB n=100
7 Correct 5 ms 25180 KB n=100
8 Correct 5 ms 25180 KB n=100
9 Correct 5 ms 25180 KB n=100
10 Correct 5 ms 25256 KB n=100
11 Correct 5 ms 25180 KB n=100
12 Correct 5 ms 25180 KB n=100
13 Correct 5 ms 25180 KB n=100
14 Correct 5 ms 25180 KB n=100
15 Correct 5 ms 25176 KB n=100
16 Correct 5 ms 25180 KB n=100
17 Correct 5 ms 25180 KB n=100
18 Correct 5 ms 25180 KB n=100
19 Correct 6 ms 25180 KB n=100
20 Correct 6 ms 25180 KB n=100
21 Correct 5 ms 25256 KB n=100
22 Correct 5 ms 25180 KB n=100
23 Correct 5 ms 25180 KB n=100
24 Correct 6 ms 25048 KB n=100
25 Correct 6 ms 25180 KB n=100
26 Correct 6 ms 25180 KB n=12
27 Correct 5 ms 25180 KB n=100
28 Correct 8 ms 25180 KB n=500
29 Correct 7 ms 25180 KB n=500
30 Correct 7 ms 25176 KB n=500
31 Correct 7 ms 25180 KB n=500
32 Correct 8 ms 25180 KB n=500
33 Correct 7 ms 25180 KB n=500
34 Correct 7 ms 25180 KB n=500
35 Correct 7 ms 25180 KB n=500
36 Correct 7 ms 25180 KB n=500
37 Correct 7 ms 25176 KB n=500
38 Correct 6 ms 25176 KB n=500
39 Correct 7 ms 25432 KB n=500
40 Correct 6 ms 25180 KB n=500
41 Correct 7 ms 25180 KB n=500
42 Correct 7 ms 25176 KB n=500
43 Correct 6 ms 25180 KB n=500
44 Correct 6 ms 25176 KB n=500
45 Correct 6 ms 25180 KB n=500
46 Correct 6 ms 25180 KB n=500
47 Correct 6 ms 25180 KB n=500
48 Correct 7 ms 25180 KB n=500
49 Correct 8 ms 25180 KB n=500
50 Correct 6 ms 25180 KB n=500
51 Correct 6 ms 25180 KB n=500
52 Correct 6 ms 25180 KB n=500
53 Correct 6 ms 25176 KB n=500
54 Correct 7 ms 25180 KB n=500
55 Correct 5 ms 25180 KB n=278
56 Correct 6 ms 25176 KB n=500
57 Correct 6 ms 25176 KB n=500
58 Correct 6 ms 25180 KB n=500
59 Correct 9 ms 25432 KB n=2000
60 Correct 10 ms 25692 KB n=2000
61 Correct 8 ms 25520 KB n=2000
62 Correct 8 ms 25436 KB n=2000
63 Correct 9 ms 25436 KB n=2000
64 Correct 9 ms 25432 KB n=2000
65 Correct 8 ms 25436 KB n=2000
66 Correct 8 ms 25688 KB n=2000
67 Correct 9 ms 25436 KB n=2000
68 Correct 10 ms 25436 KB n=2000
69 Correct 7 ms 25436 KB n=2000
70 Correct 7 ms 25436 KB n=2000
71 Correct 7 ms 25436 KB n=2000
72 Correct 7 ms 25436 KB n=2000
73 Correct 7 ms 25436 KB n=2000
74 Correct 7 ms 25436 KB n=1844
75 Correct 9 ms 25436 KB n=2000
76 Correct 10 ms 25684 KB n=2000
77 Correct 8 ms 25368 KB n=2000
78 Correct 8 ms 25432 KB n=2000
79 Correct 8 ms 25436 KB n=2000
80 Correct 8 ms 25692 KB n=2000
81 Correct 7 ms 25436 KB n=2000
82 Correct 9 ms 25436 KB n=2000
83 Correct 8 ms 25704 KB n=2000
84 Correct 9 ms 25520 KB n=2000
85 Correct 8 ms 25436 KB n=2000
86 Correct 8 ms 25436 KB n=2000
87 Correct 8 ms 25436 KB n=2000
88 Correct 7 ms 25692 KB n=2000
89 Correct 7 ms 25692 KB n=2000
90 Correct 8 ms 25692 KB n=2000
91 Correct 7 ms 25552 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25188 KB n=5
2 Correct 5 ms 25180 KB n=100
3 Correct 5 ms 25176 KB n=100
4 Correct 5 ms 25180 KB n=100
5 Correct 5 ms 25180 KB n=100
6 Correct 5 ms 25252 KB n=100
7 Correct 5 ms 25180 KB n=100
8 Correct 5 ms 25180 KB n=100
9 Correct 5 ms 25180 KB n=100
10 Correct 5 ms 25256 KB n=100
11 Correct 5 ms 25180 KB n=100
12 Correct 5 ms 25180 KB n=100
13 Correct 5 ms 25180 KB n=100
14 Correct 5 ms 25180 KB n=100
15 Correct 5 ms 25176 KB n=100
16 Correct 5 ms 25180 KB n=100
17 Correct 5 ms 25180 KB n=100
18 Correct 5 ms 25180 KB n=100
19 Correct 6 ms 25180 KB n=100
20 Correct 6 ms 25180 KB n=100
21 Correct 5 ms 25256 KB n=100
22 Correct 5 ms 25180 KB n=100
23 Correct 5 ms 25180 KB n=100
24 Correct 6 ms 25048 KB n=100
25 Correct 6 ms 25180 KB n=100
26 Correct 6 ms 25180 KB n=12
27 Correct 5 ms 25180 KB n=100
28 Correct 8 ms 25180 KB n=500
29 Correct 7 ms 25180 KB n=500
30 Correct 7 ms 25176 KB n=500
31 Correct 7 ms 25180 KB n=500
32 Correct 8 ms 25180 KB n=500
33 Correct 7 ms 25180 KB n=500
34 Correct 7 ms 25180 KB n=500
35 Correct 7 ms 25180 KB n=500
36 Correct 7 ms 25180 KB n=500
37 Correct 7 ms 25176 KB n=500
38 Correct 6 ms 25176 KB n=500
39 Correct 7 ms 25432 KB n=500
40 Correct 6 ms 25180 KB n=500
41 Correct 7 ms 25180 KB n=500
42 Correct 7 ms 25176 KB n=500
43 Correct 6 ms 25180 KB n=500
44 Correct 6 ms 25176 KB n=500
45 Correct 6 ms 25180 KB n=500
46 Correct 6 ms 25180 KB n=500
47 Correct 6 ms 25180 KB n=500
48 Correct 7 ms 25180 KB n=500
49 Correct 8 ms 25180 KB n=500
50 Correct 6 ms 25180 KB n=500
51 Correct 6 ms 25180 KB n=500
52 Correct 6 ms 25180 KB n=500
53 Correct 6 ms 25176 KB n=500
54 Correct 7 ms 25180 KB n=500
55 Correct 5 ms 25180 KB n=278
56 Correct 6 ms 25176 KB n=500
57 Correct 6 ms 25176 KB n=500
58 Correct 6 ms 25180 KB n=500
59 Correct 9 ms 25432 KB n=2000
60 Correct 10 ms 25692 KB n=2000
61 Correct 8 ms 25520 KB n=2000
62 Correct 8 ms 25436 KB n=2000
63 Correct 9 ms 25436 KB n=2000
64 Correct 9 ms 25432 KB n=2000
65 Correct 8 ms 25436 KB n=2000
66 Correct 8 ms 25688 KB n=2000
67 Correct 9 ms 25436 KB n=2000
68 Correct 10 ms 25436 KB n=2000
69 Correct 7 ms 25436 KB n=2000
70 Correct 7 ms 25436 KB n=2000
71 Correct 7 ms 25436 KB n=2000
72 Correct 7 ms 25436 KB n=2000
73 Correct 7 ms 25436 KB n=2000
74 Correct 7 ms 25436 KB n=1844
75 Correct 9 ms 25436 KB n=2000
76 Correct 10 ms 25684 KB n=2000
77 Correct 8 ms 25368 KB n=2000
78 Correct 8 ms 25432 KB n=2000
79 Correct 8 ms 25436 KB n=2000
80 Correct 8 ms 25692 KB n=2000
81 Correct 7 ms 25436 KB n=2000
82 Correct 9 ms 25436 KB n=2000
83 Correct 8 ms 25704 KB n=2000
84 Correct 9 ms 25520 KB n=2000
85 Correct 8 ms 25436 KB n=2000
86 Correct 8 ms 25436 KB n=2000
87 Correct 8 ms 25436 KB n=2000
88 Correct 7 ms 25692 KB n=2000
89 Correct 7 ms 25692 KB n=2000
90 Correct 8 ms 25692 KB n=2000
91 Correct 7 ms 25552 KB n=2000
92 Correct 533 ms 73876 KB n=200000
93 Correct 707 ms 81744 KB n=200000
94 Correct 728 ms 87304 KB n=200000
95 Correct 509 ms 73676 KB n=200000
96 Correct 512 ms 73524 KB n=200000
97 Correct 795 ms 80180 KB n=200000
98 Correct 566 ms 73536 KB n=200000
99 Correct 643 ms 73716 KB n=200000
100 Correct 537 ms 73600 KB n=200000
101 Correct 643 ms 89412 KB n=200000
102 Correct 339 ms 74844 KB n=200000
103 Correct 325 ms 74852 KB n=200000
104 Correct 340 ms 74768 KB n=200000
105 Correct 304 ms 75220 KB n=200000
106 Correct 334 ms 75136 KB n=200000
107 Correct 335 ms 75192 KB n=200000
108 Correct 609 ms 73624 KB n=200000
109 Correct 625 ms 73588 KB n=200000
110 Correct 653 ms 73688 KB n=200000
111 Correct 592 ms 73172 KB n=200000
112 Correct 594 ms 87880 KB n=200000
113 Correct 632 ms 80304 KB n=200000
114 Correct 545 ms 73268 KB n=200000
115 Correct 739 ms 76952 KB n=200000
116 Correct 526 ms 73868 KB n=200000
117 Correct 580 ms 88520 KB n=200000
118 Correct 790 ms 78960 KB n=200000
119 Correct 516 ms 73676 KB n=200000
120 Correct 584 ms 88476 KB n=200000
121 Correct 542 ms 89004 KB n=200000
122 Correct 703 ms 88724 KB n=200000
123 Correct 393 ms 75156 KB n=200000
124 Correct 129 ms 41044 KB n=25264