oj.uz

Submission #167568

# Submission time Handle Problem Language Result Execution time Memory
167568 2019-12-09T02:39:03 Z Flying_dragon_02 Birthday gift (IZhO18_treearray) C++14
100 / 100
 2061 ms 71320 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair< int, int > ii;

const int N = 2e5 + 5;

int n, m, q, par[N][20], f[N], a[N];

vector< int > graph[N];

multiset< pair< int, ii > > mst;
multiset< pair< int, ii > >::iterator it;

void dfs(int u, int p) {
    for(int i = 0; i < (int)( graph[u].size() ); i++) {
        int v = graph[u][i];
        if( v == p ) continue;
        par[v][0] = u;
        f[v] = f[u] + 1;
        dfs( v, u );
    }
}

void initLCA() {
    for(int j = 1; j < 20; j++) {
        for(int i = 1; i <= n; i++)
            par[i][j] = par[ par[i][ j - 1 ] ][ j - 1 ];
    }
}

int findLCA(int u, int v) {
    if( f[u] < f[v] ) swap( u, v );
    for(int i = 19; i >= 0; i--) {
        if( par[u][i] != 0 && f[ par[u][i] ] >= f[v] )
            u = par[u][i];
    }
    if( u == v ) return u;
    for(int i = 19; i >= 0; i-- ) {
        if( par[u][i] != 0 && par[v][i] != 0 && par[u][i] != par[v][i] ) {
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}

int main() {
    cin.tie(0), ios_base::sync_with_stdio(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].pb( v );
        graph[v].pb( u );
    }
    dfs( 1, 1 );
    initLCA();
    for(int i = 1; i <= m; i++) {
        cin >> a[i];
        mst.insert( mp( a[i], mp( i, i ) ) );
    }
    for(int i = 1; i < m; i++) {
        int u = findLCA( a[i], a[i + 1] );
        mst.insert( mp( u, mp( i, i + 1 ) ) );
    }
    while(q--) {
        int type;
        cin >> type;
        if( type == 1 ) {
            int pos, v, u ;
            cin >> pos >> v;
            if( pos > 1 ) {
                u = findLCA( a[ pos ], a[pos - 1] );
                it = mst.find( mp( u, mp( pos - 1, pos ) ) );
                mst.erase( it );
            }
            it = mst.find( mp( a[ pos ], mp( pos, pos ) ) );
            mst.erase( it );
            if( pos < m ) {
                u = findLCA( a[ pos ], a[pos + 1] );
                it = mst.find( mp( u, mp( pos , pos + 1 ) ) );
                mst.erase( it );
            }
            a[pos] = v;
            if( pos > 1 ) {
                u = findLCA( a[ pos ], a[pos - 1] );
                it = mst.insert( mp( u, mp( pos - 1, pos ) ) );
            }
            it = mst.insert( mp( a[ pos ], mp( pos, pos ) ) );
            if( pos < m ) {
                u = findLCA( a[ pos ], a[pos + 1] );
                it = mst.insert( mp( u, mp( pos , pos + 1 ) ) );
            }
        }
        else {
            int l, r, v;
            cin >> l >> r >> v;
            it = mst.lower_bound( mp( v, mp( l, l ) ) );
            if( it == mst.end() || (*it).fi != v ) {
                cout << "-1 -1\n";
                continue;
            }
            if( (*it).se.fi >= l && (*it).se.se <= r )
                cout << (*it).se.fi << " " << (*it).se.se << "\n";
            else
                cout << "-1 -1\n";
        }
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB n=5
2 Correct 6 ms 5112 KB n=100
3 Correct 6 ms 5112 KB n=100
4 Correct 6 ms 5112 KB n=100
5 Correct 6 ms 5112 KB n=100
6 Correct 6 ms 5108 KB n=100
7 Correct 7 ms 5112 KB n=100
8 Correct 7 ms 5112 KB n=100
9 Correct 6 ms 5112 KB n=100
10 Correct 6 ms 5112 KB n=100
11 Correct 6 ms 5112 KB n=100
12 Correct 6 ms 5112 KB n=100
13 Correct 6 ms 5112 KB n=100
14 Correct 6 ms 5112 KB n=100
15 Correct 6 ms 5112 KB n=100
16 Correct 6 ms 5116 KB n=100
17 Correct 6 ms 5112 KB n=100
18 Correct 6 ms 5240 KB n=100
19 Correct 6 ms 5112 KB n=100
20 Correct 6 ms 5112 KB n=100
21 Correct 6 ms 5112 KB n=100
22 Correct 6 ms 5112 KB n=100
23 Correct 7 ms 5112 KB n=100
24 Correct 6 ms 5112 KB n=100
25 Correct 6 ms 5112 KB n=100
26 Correct 6 ms 4984 KB n=12
27 Correct 6 ms 5084 KB n=100

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB n=5
2 Correct 6 ms 5112 KB n=100
3 Correct 6 ms 5112 KB n=100
4 Correct 6 ms 5112 KB n=100
5 Correct 6 ms 5112 KB n=100
6 Correct 6 ms 5108 KB n=100
7 Correct 7 ms 5112 KB n=100
8 Correct 7 ms 5112 KB n=100
9 Correct 6 ms 5112 KB n=100
10 Correct 6 ms 5112 KB n=100
11 Correct 6 ms 5112 KB n=100
12 Correct 6 ms 5112 KB n=100
13 Correct 6 ms 5112 KB n=100
14 Correct 6 ms 5112 KB n=100
15 Correct 6 ms 5112 KB n=100
16 Correct 6 ms 5116 KB n=100
17 Correct 6 ms 5112 KB n=100
18 Correct 6 ms 5240 KB n=100
19 Correct 6 ms 5112 KB n=100
20 Correct 6 ms 5112 KB n=100
21 Correct 6 ms 5112 KB n=100
22 Correct 6 ms 5112 KB n=100
23 Correct 7 ms 5112 KB n=100
24 Correct 6 ms 5112 KB n=100
25 Correct 6 ms 5112 KB n=100
26 Correct 6 ms 4984 KB n=12
27 Correct 6 ms 5084 KB n=100
28 Correct 7 ms 5112 KB n=500
29 Correct 7 ms 5240 KB n=500
30 Correct 8 ms 5240 KB n=500
31 Correct 9 ms 5128 KB n=500
32 Correct 7 ms 5152 KB n=500
33 Correct 7 ms 5240 KB n=500
34 Correct 7 ms 5240 KB n=500
35 Correct 7 ms 5240 KB n=500
36 Correct 7 ms 5112 KB n=500
37 Correct 7 ms 5240 KB n=500
38 Correct 7 ms 5240 KB n=500
39 Correct 7 ms 5160 KB n=500
40 Correct 7 ms 5112 KB n=500
41 Correct 6 ms 5240 KB n=500
42 Correct 7 ms 5240 KB n=500
43 Correct 7 ms 5240 KB n=500
44 Correct 7 ms 5240 KB n=500
45 Correct 7 ms 5240 KB n=500
46 Correct 7 ms 5240 KB n=500
47 Correct 7 ms 5240 KB n=500
48 Correct 7 ms 5112 KB n=500
49 Correct 7 ms 5240 KB n=500
50 Correct 7 ms 5112 KB n=500
51 Correct 7 ms 5240 KB n=500
52 Correct 7 ms 5240 KB n=500
53 Correct 7 ms 5240 KB n=500
54 Correct 7 ms 5240 KB n=500
55 Correct 7 ms 5112 KB n=278
56 Correct 7 ms 5240 KB n=500
57 Correct 7 ms 5240 KB n=500
58 Correct 7 ms 5240 KB n=500
59 Correct 10 ms 5628 KB n=2000
60 Correct 13 ms 5624 KB n=2000
61 Correct 12 ms 5624 KB n=2000
62 Correct 13 ms 5624 KB n=2000
63 Correct 12 ms 5624 KB n=2000
64 Correct 11 ms 5624 KB n=2000
65 Correct 13 ms 5596 KB n=2000
66 Correct 13 ms 5624 KB n=2000
67 Correct 12 ms 5668 KB n=2000
68 Correct 12 ms 5624 KB n=2000
69 Correct 9 ms 5624 KB n=2000
70 Correct 9 ms 5624 KB n=2000
71 Correct 9 ms 5624 KB n=2000
72 Correct 9 ms 5628 KB n=2000
73 Correct 9 ms 5624 KB n=2000
74 Correct 10 ms 5496 KB n=1844
75 Correct 9 ms 5624 KB n=2000
76 Correct 11 ms 5624 KB n=2000
77 Correct 11 ms 5624 KB n=2000
78 Correct 11 ms 5624 KB n=2000
79 Correct 10 ms 5624 KB n=2000
80 Correct 12 ms 5752 KB n=2000
81 Correct 11 ms 5624 KB n=2000
82 Correct 11 ms 5648 KB n=2000
83 Correct 12 ms 5624 KB n=2000
84 Correct 10 ms 5624 KB n=2000
85 Correct 12 ms 5752 KB n=2000
86 Correct 12 ms 5624 KB n=2000
87 Correct 10 ms 5624 KB n=2000
88 Correct 11 ms 5752 KB n=2000
89 Correct 11 ms 5624 KB n=2000
90 Correct 11 ms 5752 KB n=2000
91 Correct 9 ms 5624 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB n=5
2 Correct 6 ms 5112 KB n=100
3 Correct 6 ms 5112 KB n=100
4 Correct 6 ms 5112 KB n=100
5 Correct 6 ms 5112 KB n=100
6 Correct 6 ms 5108 KB n=100
7 Correct 7 ms 5112 KB n=100
8 Correct 7 ms 5112 KB n=100
9 Correct 6 ms 5112 KB n=100
10 Correct 6 ms 5112 KB n=100
11 Correct 6 ms 5112 KB n=100
12 Correct 6 ms 5112 KB n=100
13 Correct 6 ms 5112 KB n=100
14 Correct 6 ms 5112 KB n=100
15 Correct 6 ms 5112 KB n=100
16 Correct 6 ms 5116 KB n=100
17 Correct 6 ms 5112 KB n=100
18 Correct 6 ms 5240 KB n=100
19 Correct 6 ms 5112 KB n=100
20 Correct 6 ms 5112 KB n=100
21 Correct 6 ms 5112 KB n=100
22 Correct 6 ms 5112 KB n=100
23 Correct 7 ms 5112 KB n=100
24 Correct 6 ms 5112 KB n=100
25 Correct 6 ms 5112 KB n=100
26 Correct 6 ms 4984 KB n=12
27 Correct 6 ms 5084 KB n=100
28 Correct 7 ms 5112 KB n=500
29 Correct 7 ms 5240 KB n=500
30 Correct 8 ms 5240 KB n=500
31 Correct 9 ms 5128 KB n=500
32 Correct 7 ms 5152 KB n=500
33 Correct 7 ms 5240 KB n=500
34 Correct 7 ms 5240 KB n=500
35 Correct 7 ms 5240 KB n=500
36 Correct 7 ms 5112 KB n=500
37 Correct 7 ms 5240 KB n=500
38 Correct 7 ms 5240 KB n=500
39 Correct 7 ms 5160 KB n=500
40 Correct 7 ms 5112 KB n=500
41 Correct 6 ms 5240 KB n=500
42 Correct 7 ms 5240 KB n=500
43 Correct 7 ms 5240 KB n=500
44 Correct 7 ms 5240 KB n=500
45 Correct 7 ms 5240 KB n=500
46 Correct 7 ms 5240 KB n=500
47 Correct 7 ms 5240 KB n=500
48 Correct 7 ms 5112 KB n=500
49 Correct 7 ms 5240 KB n=500
50 Correct 7 ms 5112 KB n=500
51 Correct 7 ms 5240 KB n=500
52 Correct 7 ms 5240 KB n=500
53 Correct 7 ms 5240 KB n=500
54 Correct 7 ms 5240 KB n=500
55 Correct 7 ms 5112 KB n=278
56 Correct 7 ms 5240 KB n=500
57 Correct 7 ms 5240 KB n=500
58 Correct 7 ms 5240 KB n=500
59 Correct 10 ms 5628 KB n=2000
60 Correct 13 ms 5624 KB n=2000
61 Correct 12 ms 5624 KB n=2000
62 Correct 13 ms 5624 KB n=2000
63 Correct 12 ms 5624 KB n=2000
64 Correct 11 ms 5624 KB n=2000
65 Correct 13 ms 5596 KB n=2000
66 Correct 13 ms 5624 KB n=2000
67 Correct 12 ms 5668 KB n=2000
68 Correct 12 ms 5624 KB n=2000
69 Correct 9 ms 5624 KB n=2000
70 Correct 9 ms 5624 KB n=2000
71 Correct 9 ms 5624 KB n=2000
72 Correct 9 ms 5628 KB n=2000
73 Correct 9 ms 5624 KB n=2000
74 Correct 10 ms 5496 KB n=1844
75 Correct 9 ms 5624 KB n=2000
76 Correct 11 ms 5624 KB n=2000
77 Correct 11 ms 5624 KB n=2000
78 Correct 11 ms 5624 KB n=2000
79 Correct 10 ms 5624 KB n=2000
80 Correct 12 ms 5752 KB n=2000
81 Correct 11 ms 5624 KB n=2000
82 Correct 11 ms 5648 KB n=2000
83 Correct 12 ms 5624 KB n=2000
84 Correct 10 ms 5624 KB n=2000
85 Correct 12 ms 5752 KB n=2000
86 Correct 12 ms 5624 KB n=2000
87 Correct 10 ms 5624 KB n=2000
88 Correct 11 ms 5752 KB n=2000
89 Correct 11 ms 5624 KB n=2000
90 Correct 11 ms 5752 KB n=2000
91 Correct 9 ms 5624 KB n=2000
92 Correct 1025 ms 56904 KB n=200000
93 Correct 2061 ms 63956 KB n=200000
94 Correct 1838 ms 67168 KB n=200000
95 Correct 1002 ms 57184 KB n=200000
96 Correct 1065 ms 57144 KB n=200000
97 Correct 1929 ms 63344 KB n=200000
98 Correct 1363 ms 57632 KB n=200000
99 Correct 1341 ms 60928 KB n=200000
100 Correct 1097 ms 58696 KB n=200000
101 Correct 1966 ms 71320 KB n=200000
102 Correct 640 ms 63056 KB n=200000
103 Correct 650 ms 63096 KB n=200000
104 Correct 682 ms 62780 KB n=200000
105 Correct 619 ms 63236 KB n=200000
106 Correct 635 ms 63352 KB n=200000
107 Correct 587 ms 63224 KB n=200000
108 Correct 1263 ms 61792 KB n=200000
109 Correct 1193 ms 61856 KB n=200000
110 Correct 1164 ms 61760 KB n=200000
111 Correct 1033 ms 59200 KB n=200000
112 Correct 1916 ms 69632 KB n=200000
113 Correct 1815 ms 65960 KB n=200000
114 Correct 1041 ms 59004 KB n=200000
115 Correct 1967 ms 63608 KB n=200000
116 Correct 1052 ms 58836 KB n=200000
117 Correct 1985 ms 70648 KB n=200000
118 Correct 1884 ms 64828 KB n=200000
119 Correct 1029 ms 61880 KB n=200000
120 Correct 1796 ms 70000 KB n=200000
121 Correct 1805 ms 69620 KB n=200000
122 Correct 1884 ms 70680 KB n=200000
123 Correct 573 ms 62996 KB n=200000
124 Correct 376 ms 22804 KB n=25264