oj.uz

Submission #863886

# Submission time Handle Problem Language Result Execution time Memory
863886 2023-10-21T10:35:29 Z nnhzzz Birthday gift (IZhO18_treearray) C++14
100 / 100
 734 ms 88916 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;}

inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
template<class T> 
istream& operator>> (istream &stream, int x) {
    return x = readInt(), stream;
} 

/*
----------------------------------------------------------------
    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:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:148:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:152:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |         freopen(name1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:153:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |         freopen(name1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25180 KB n=5
2 Correct 6 ms 25044 KB n=100
3 Correct 6 ms 25180 KB n=100
4 Correct 5 ms 25176 KB n=100
5 Correct 5 ms 25176 KB n=100
6 Correct 5 ms 25272 KB n=100
7 Correct 5 ms 25176 KB n=100
8 Correct 5 ms 25180 KB n=100
9 Correct 6 ms 25180 KB n=100
10 Correct 6 ms 25216 KB n=100
11 Correct 6 ms 25216 KB n=100
12 Correct 5 ms 25180 KB n=100
13 Correct 5 ms 25272 KB n=100
14 Correct 6 ms 25176 KB n=100
15 Correct 5 ms 25180 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 5 ms 25256 KB n=100
20 Correct 5 ms 25180 KB n=100
21 Correct 5 ms 25176 KB n=100
22 Correct 5 ms 25280 KB n=100
23 Correct 5 ms 25176 KB n=100
24 Correct 6 ms 25180 KB n=100
25 Correct 5 ms 25180 KB n=100
26 Correct 5 ms 25176 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 25180 KB n=5
2 Correct 6 ms 25044 KB n=100
3 Correct 6 ms 25180 KB n=100
4 Correct 5 ms 25176 KB n=100
5 Correct 5 ms 25176 KB n=100
6 Correct 5 ms 25272 KB n=100
7 Correct 5 ms 25176 KB n=100
8 Correct 5 ms 25180 KB n=100
9 Correct 6 ms 25180 KB n=100
10 Correct 6 ms 25216 KB n=100
11 Correct 6 ms 25216 KB n=100
12 Correct 5 ms 25180 KB n=100
13 Correct 5 ms 25272 KB n=100
14 Correct 6 ms 25176 KB n=100
15 Correct 5 ms 25180 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 5 ms 25256 KB n=100
20 Correct 5 ms 25180 KB n=100
21 Correct 5 ms 25176 KB n=100
22 Correct 5 ms 25280 KB n=100
23 Correct 5 ms 25176 KB n=100
24 Correct 6 ms 25180 KB n=100
25 Correct 5 ms 25180 KB n=100
26 Correct 5 ms 25176 KB n=12
27 Correct 5 ms 25180 KB n=100
28 Correct 6 ms 25180 KB n=500
29 Correct 6 ms 25180 KB n=500
30 Correct 6 ms 25176 KB n=500
31 Correct 6 ms 25180 KB n=500
32 Correct 7 ms 25180 KB n=500
33 Correct 6 ms 25176 KB n=500
34 Correct 7 ms 25180 KB n=500
35 Correct 6 ms 25180 KB n=500
36 Correct 6 ms 25180 KB n=500
37 Correct 6 ms 25176 KB n=500
38 Correct 6 ms 25180 KB n=500
39 Correct 6 ms 25180 KB n=500
40 Correct 6 ms 25288 KB n=500
41 Correct 7 ms 25272 KB n=500
42 Correct 6 ms 25180 KB n=500
43 Correct 6 ms 25180 KB n=500
44 Correct 6 ms 25180 KB n=500
45 Correct 6 ms 25180 KB n=500
46 Correct 7 ms 25176 KB n=500
47 Correct 6 ms 25180 KB n=500
48 Correct 7 ms 25180 KB n=500
49 Correct 7 ms 25252 KB n=500
50 Correct 6 ms 25296 KB n=500
51 Correct 7 ms 25300 KB n=500
52 Correct 6 ms 25180 KB n=500
53 Correct 6 ms 25180 KB n=500
54 Correct 7 ms 25264 KB n=500
55 Correct 7 ms 25180 KB n=278
56 Correct 6 ms 25180 KB n=500
57 Correct 6 ms 25180 KB n=500
58 Correct 7 ms 25180 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25180 KB n=5
2 Correct 6 ms 25044 KB n=100
3 Correct 6 ms 25180 KB n=100
4 Correct 5 ms 25176 KB n=100
5 Correct 5 ms 25176 KB n=100
6 Correct 5 ms 25272 KB n=100
7 Correct 5 ms 25176 KB n=100
8 Correct 5 ms 25180 KB n=100
9 Correct 6 ms 25180 KB n=100
10 Correct 6 ms 25216 KB n=100
11 Correct 6 ms 25216 KB n=100
12 Correct 5 ms 25180 KB n=100
13 Correct 5 ms 25272 KB n=100
14 Correct 6 ms 25176 KB n=100
15 Correct 5 ms 25180 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 5 ms 25256 KB n=100
20 Correct 5 ms 25180 KB n=100
21 Correct 5 ms 25176 KB n=100
22 Correct 5 ms 25280 KB n=100
23 Correct 5 ms 25176 KB n=100
24 Correct 6 ms 25180 KB n=100
25 Correct 5 ms 25180 KB n=100
26 Correct 5 ms 25176 KB n=12
27 Correct 5 ms 25180 KB n=100
28 Correct 6 ms 25180 KB n=500
29 Correct 6 ms 25180 KB n=500
30 Correct 6 ms 25176 KB n=500
31 Correct 6 ms 25180 KB n=500
32 Correct 7 ms 25180 KB n=500
33 Correct 6 ms 25176 KB n=500
34 Correct 7 ms 25180 KB n=500
35 Correct 6 ms 25180 KB n=500
36 Correct 6 ms 25180 KB n=500
37 Correct 6 ms 25176 KB n=500
38 Correct 6 ms 25180 KB n=500
39 Correct 6 ms 25180 KB n=500
40 Correct 6 ms 25288 KB n=500
41 Correct 7 ms 25272 KB n=500
42 Correct 6 ms 25180 KB n=500
43 Correct 6 ms 25180 KB n=500
44 Correct 6 ms 25180 KB n=500
45 Correct 6 ms 25180 KB n=500
46 Correct 7 ms 25176 KB n=500
47 Correct 6 ms 25180 KB n=500
48 Correct 7 ms 25180 KB n=500
49 Correct 7 ms 25252 KB n=500
50 Correct 6 ms 25296 KB n=500
51 Correct 7 ms 25300 KB n=500
52 Correct 6 ms 25180 KB n=500
53 Correct 6 ms 25180 KB n=500
54 Correct 7 ms 25264 KB n=500
55 Correct 7 ms 25180 KB n=278
56 Correct 6 ms 25180 KB n=500
57 Correct 6 ms 25180 KB n=500
58 Correct 7 ms 25180 KB n=500
59 Correct 7 ms 25436 KB n=2000
60 Correct 8 ms 25692 KB n=2000
61 Correct 9 ms 25692 KB n=2000
62 Correct 8 ms 25436 KB n=2000
63 Correct 8 ms 25436 KB n=2000
64 Correct 7 ms 25432 KB n=2000
65 Correct 8 ms 25436 KB n=2000
66 Correct 7 ms 25676 KB n=2000
67 Correct 8 ms 25688 KB n=2000
68 Correct 7 ms 25436 KB n=2000
69 Correct 8 ms 25436 KB n=2000
70 Correct 7 ms 25436 KB n=2000
71 Correct 8 ms 25432 KB n=2000
72 Correct 7 ms 25436 KB n=2000
73 Correct 8 ms 25596 KB n=2000
74 Correct 7 ms 25436 KB n=1844
75 Correct 7 ms 25436 KB n=2000
76 Correct 8 ms 25444 KB n=2000
77 Correct 8 ms 25432 KB n=2000
78 Correct 7 ms 25688 KB n=2000
79 Correct 7 ms 25432 KB n=2000
80 Correct 7 ms 25524 KB n=2000
81 Correct 7 ms 25436 KB n=2000
82 Correct 7 ms 25436 KB n=2000
83 Correct 9 ms 25688 KB n=2000
84 Correct 9 ms 25888 KB n=2000
85 Correct 7 ms 25436 KB n=2000
86 Correct 9 ms 25436 KB n=2000
87 Correct 7 ms 25432 KB n=2000
88 Correct 9 ms 25760 KB n=2000
89 Correct 8 ms 25692 KB n=2000
90 Correct 7 ms 25692 KB n=2000
91 Correct 7 ms 25436 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25180 KB n=5
2 Correct 6 ms 25044 KB n=100
3 Correct 6 ms 25180 KB n=100
4 Correct 5 ms 25176 KB n=100
5 Correct 5 ms 25176 KB n=100
6 Correct 5 ms 25272 KB n=100
7 Correct 5 ms 25176 KB n=100
8 Correct 5 ms 25180 KB n=100
9 Correct 6 ms 25180 KB n=100
10 Correct 6 ms 25216 KB n=100
11 Correct 6 ms 25216 KB n=100
12 Correct 5 ms 25180 KB n=100
13 Correct 5 ms 25272 KB n=100
14 Correct 6 ms 25176 KB n=100
15 Correct 5 ms 25180 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 5 ms 25256 KB n=100
20 Correct 5 ms 25180 KB n=100
21 Correct 5 ms 25176 KB n=100
22 Correct 5 ms 25280 KB n=100
23 Correct 5 ms 25176 KB n=100
24 Correct 6 ms 25180 KB n=100
25 Correct 5 ms 25180 KB n=100
26 Correct 5 ms 25176 KB n=12
27 Correct 5 ms 25180 KB n=100
28 Correct 6 ms 25180 KB n=500
29 Correct 6 ms 25180 KB n=500
30 Correct 6 ms 25176 KB n=500
31 Correct 6 ms 25180 KB n=500
32 Correct 7 ms 25180 KB n=500
33 Correct 6 ms 25176 KB n=500
34 Correct 7 ms 25180 KB n=500
35 Correct 6 ms 25180 KB n=500
36 Correct 6 ms 25180 KB n=500
37 Correct 6 ms 25176 KB n=500
38 Correct 6 ms 25180 KB n=500
39 Correct 6 ms 25180 KB n=500
40 Correct 6 ms 25288 KB n=500
41 Correct 7 ms 25272 KB n=500
42 Correct 6 ms 25180 KB n=500
43 Correct 6 ms 25180 KB n=500
44 Correct 6 ms 25180 KB n=500
45 Correct 6 ms 25180 KB n=500
46 Correct 7 ms 25176 KB n=500
47 Correct 6 ms 25180 KB n=500
48 Correct 7 ms 25180 KB n=500
49 Correct 7 ms 25252 KB n=500
50 Correct 6 ms 25296 KB n=500
51 Correct 7 ms 25300 KB n=500
52 Correct 6 ms 25180 KB n=500
53 Correct 6 ms 25180 KB n=500
54 Correct 7 ms 25264 KB n=500
55 Correct 7 ms 25180 KB n=278
56 Correct 6 ms 25180 KB n=500
57 Correct 6 ms 25180 KB n=500
58 Correct 7 ms 25180 KB n=500
59 Correct 7 ms 25436 KB n=2000
60 Correct 8 ms 25692 KB n=2000
61 Correct 9 ms 25692 KB n=2000
62 Correct 8 ms 25436 KB n=2000
63 Correct 8 ms 25436 KB n=2000
64 Correct 7 ms 25432 KB n=2000
65 Correct 8 ms 25436 KB n=2000
66 Correct 7 ms 25676 KB n=2000
67 Correct 8 ms 25688 KB n=2000
68 Correct 7 ms 25436 KB n=2000
69 Correct 8 ms 25436 KB n=2000
70 Correct 7 ms 25436 KB n=2000
71 Correct 8 ms 25432 KB n=2000
72 Correct 7 ms 25436 KB n=2000
73 Correct 8 ms 25596 KB n=2000
74 Correct 7 ms 25436 KB n=1844
75 Correct 7 ms 25436 KB n=2000
76 Correct 8 ms 25444 KB n=2000
77 Correct 8 ms 25432 KB n=2000
78 Correct 7 ms 25688 KB n=2000
79 Correct 7 ms 25432 KB n=2000
80 Correct 7 ms 25524 KB n=2000
81 Correct 7 ms 25436 KB n=2000
82 Correct 7 ms 25436 KB n=2000
83 Correct 9 ms 25688 KB n=2000
84 Correct 9 ms 25888 KB n=2000
85 Correct 7 ms 25436 KB n=2000
86 Correct 9 ms 25436 KB n=2000
87 Correct 7 ms 25432 KB n=2000
88 Correct 9 ms 25760 KB n=2000
89 Correct 8 ms 25692 KB n=2000
90 Correct 7 ms 25692 KB n=2000
91 Correct 7 ms 25436 KB n=2000
92 Correct 489 ms 73808 KB n=200000
93 Correct 601 ms 81748 KB n=200000
94 Correct 551 ms 87436 KB n=200000
95 Correct 496 ms 73512 KB n=200000
96 Correct 477 ms 73236 KB n=200000
97 Correct 734 ms 79856 KB n=200000
98 Correct 478 ms 73220 KB n=200000
99 Correct 572 ms 73512 KB n=200000
100 Correct 564 ms 73344 KB n=200000
101 Correct 504 ms 88916 KB n=200000
102 Correct 269 ms 74404 KB n=200000
103 Correct 289 ms 74492 KB n=200000
104 Correct 268 ms 74460 KB n=200000
105 Correct 278 ms 74836 KB n=200000
106 Correct 267 ms 74836 KB n=200000
107 Correct 273 ms 74836 KB n=200000
108 Correct 494 ms 73160 KB n=200000
109 Correct 473 ms 73300 KB n=200000
110 Correct 473 ms 73260 KB n=200000
111 Correct 439 ms 72840 KB n=200000
112 Correct 479 ms 87168 KB n=200000
113 Correct 529 ms 79628 KB n=200000
114 Correct 446 ms 72820 KB n=200000
115 Correct 562 ms 76116 KB n=200000
116 Correct 434 ms 73420 KB n=200000
117 Correct 532 ms 87892 KB n=200000
118 Correct 552 ms 77856 KB n=200000
119 Correct 439 ms 73416 KB n=200000
120 Correct 456 ms 88144 KB n=200000
121 Correct 441 ms 88148 KB n=200000
122 Correct 451 ms 88444 KB n=200000
123 Correct 278 ms 74872 KB n=200000
124 Correct 99 ms 41044 KB n=25264