oj.uz

Submission #416596

# Submission time Handle Problem Language Result Execution time Memory
416596 2021-06-02T16:45:39 Z Lawliet Birthday gift (IZhO18_treearray) C++17
100 / 100
 1512 ms 87092 KB 
#include <bits/stdc++.h>

using namespace std;

const int LOG = 20;
const int MAXN = 200010;

int n, m, q;

int v[MAXN];
int depth[MAXN];
int tab[LOG][MAXN];

vector<int> adj[MAXN];

set<int> nodes[MAXN];
set<int> nodePair[MAXN];

void DFS(int node, int p, int d)
{
    depth[node] = d;
    tab[0][node] = p;

    for(int k = 1 ; k < LOG ; k++)
        tab[k][node] = tab[k - 1][tab[k - 1][node]];

    for(int i = 0 ; i < (int)adj[node].size() ; i++)
    {
        int viz = adj[node][i];

        if( viz != p )
            DFS( viz , node , d + 1 );
    }
}

int LCA(int U, int V)
{
    if( depth[U] < depth[V] )
        swap( U , V );

    int d = depth[U] - depth[V];

    for(int k = 0 ; k < LOG ; k++)
        if( d & (1 << k) ) U = tab[k][U];

    if( U == V ) return U;

    for(int k = LOG - 1 ; k >= 0 ; k--)
        if( tab[k][U] != tab[k][V] ) U = tab[k][U], V = tab[k][V];

    return tab[0][U];
}

void update(int pos, int node)
{
    nodes[ v[pos] ].erase( pos );
    nodes[ node ].insert( pos );

    if( pos != 1 )
    {
        nodePair[ LCA( v[pos - 1] , v[pos] ) ].erase( pos - 1 );
        nodePair[ LCA( v[pos - 1] , node ) ].insert( pos - 1 );
    }
    if( pos != m )
    {
        nodePair[ LCA( v[pos + 1] , v[pos] ) ].erase( pos );
        nodePair[ LCA( v[pos + 1] , node ) ].insert( pos );
    }

    v[pos] = node;
}

void query(int l, int r, int node, int& ansL, int& ansR)
{
    ansL = ansR = -1;

    auto it = nodes[node].lower_bound(l);

    if( it != nodes[node].end() && *it <= r )
        ansL = ansR = *it;

    it = nodePair[node].lower_bound(l);

    if( it != nodePair[node].end() && *it < r )
        ansL = *it, ansR = *it + 1;
}

int main()
{
    scanf("%d %d %d",&n,&m,&q);

    for(int i = 1 ; i < n ; i++)
    {
        int U, V;
        scanf("%d %d",&U,&V);

        adj[U].push_back( V );
        adj[V].push_back( U );
    }

    DFS( 1 , 1 , 0 );

    for(int i = 1 ; i <= m ; i++)
    {
        scanf("%d",&v[i]);
        nodes[ v[i] ].insert( i );
    }

    for(int i = 1 ; i < m ; i++)
        nodePair[ LCA( v[i] , v[i + 1] ) ].insert( i );

    for(int i = 1 ; i <= q ; i++)
    {
        int type;
        scanf("%d",&type);

        if( type == 1 )
        {
            int pos, node;
            scanf("%d %d",&pos,&node);

            update( pos , node );
        }
        if( type == 2 )
        {
            int l, r, node;
            scanf("%d %d %d",&l,&r,&node);

            int ansL, ansR;
            query( l , r , node , ansL , ansR );

            printf("%d %d\n",ansL,ansR);
        }
    }
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     scanf("%d %d %d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
treearray.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         scanf("%d %d",&U,&V);
      |         ~~~~~^~~~~~~~~~~~~~~
treearray.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         scanf("%d",&v[i]);
      |         ~~~~~^~~~~~~~~~~~
treearray.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         scanf("%d",&type);
      |         ~~~~~^~~~~~~~~~~~
treearray.cpp:120:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |             scanf("%d %d",&pos,&node);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~
treearray.cpp:127:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |             scanf("%d %d %d",&l,&r,&node);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23884 KB n=5
2 Correct 13 ms 23920 KB n=100
3 Correct 16 ms 23888 KB n=100
4 Correct 15 ms 23912 KB n=100
5 Correct 13 ms 23884 KB n=100
6 Correct 13 ms 23884 KB n=100
7 Correct 13 ms 23916 KB n=100
8 Correct 13 ms 23836 KB n=100
9 Correct 13 ms 23884 KB n=100
10 Correct 15 ms 23884 KB n=100
11 Correct 14 ms 23884 KB n=100
12 Correct 13 ms 23880 KB n=100
13 Correct 15 ms 23884 KB n=100
14 Correct 14 ms 23820 KB n=100
15 Correct 13 ms 23920 KB n=100
16 Correct 13 ms 23888 KB n=100
17 Correct 13 ms 23884 KB n=100
18 Correct 14 ms 23884 KB n=100
19 Correct 13 ms 23912 KB n=100
20 Correct 13 ms 23884 KB n=100
21 Correct 14 ms 23836 KB n=100
22 Correct 13 ms 23912 KB n=100
23 Correct 13 ms 23920 KB n=100
24 Correct 13 ms 23884 KB n=100
25 Correct 14 ms 23888 KB n=100
26 Correct 13 ms 23912 KB n=12
27 Correct 14 ms 23832 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23884 KB n=5
2 Correct 13 ms 23920 KB n=100
3 Correct 16 ms 23888 KB n=100
4 Correct 15 ms 23912 KB n=100
5 Correct 13 ms 23884 KB n=100
6 Correct 13 ms 23884 KB n=100
7 Correct 13 ms 23916 KB n=100
8 Correct 13 ms 23836 KB n=100
9 Correct 13 ms 23884 KB n=100
10 Correct 15 ms 23884 KB n=100
11 Correct 14 ms 23884 KB n=100
12 Correct 13 ms 23880 KB n=100
13 Correct 15 ms 23884 KB n=100
14 Correct 14 ms 23820 KB n=100
15 Correct 13 ms 23920 KB n=100
16 Correct 13 ms 23888 KB n=100
17 Correct 13 ms 23884 KB n=100
18 Correct 14 ms 23884 KB n=100
19 Correct 13 ms 23912 KB n=100
20 Correct 13 ms 23884 KB n=100
21 Correct 14 ms 23836 KB n=100
22 Correct 13 ms 23912 KB n=100
23 Correct 13 ms 23920 KB n=100
24 Correct 13 ms 23884 KB n=100
25 Correct 14 ms 23888 KB n=100
26 Correct 13 ms 23912 KB n=12
27 Correct 14 ms 23832 KB n=100
28 Correct 14 ms 23924 KB n=500
29 Correct 14 ms 24012 KB n=500
30 Correct 15 ms 24000 KB n=500
31 Correct 14 ms 23932 KB n=500
32 Correct 16 ms 23936 KB n=500
33 Correct 15 ms 23956 KB n=500
34 Correct 14 ms 23964 KB n=500
35 Correct 14 ms 24052 KB n=500
36 Correct 14 ms 23924 KB n=500
37 Correct 14 ms 24024 KB n=500
38 Correct 15 ms 24012 KB n=500
39 Correct 14 ms 24012 KB n=500
40 Correct 14 ms 24008 KB n=500
41 Correct 14 ms 23936 KB n=500
42 Correct 15 ms 24012 KB n=500
43 Correct 14 ms 23920 KB n=500
44 Correct 16 ms 24012 KB n=500
45 Correct 14 ms 23920 KB n=500
46 Correct 14 ms 24088 KB n=500
47 Correct 14 ms 23984 KB n=500
48 Correct 14 ms 23928 KB n=500
49 Correct 14 ms 24012 KB n=500
50 Correct 14 ms 23956 KB n=500
51 Correct 14 ms 23964 KB n=500
52 Correct 14 ms 24012 KB n=500
53 Correct 14 ms 24012 KB n=500
54 Correct 14 ms 24028 KB n=500
55 Correct 13 ms 23884 KB n=278
56 Correct 14 ms 23976 KB n=500
57 Correct 14 ms 24012 KB n=500
58 Correct 14 ms 24012 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23884 KB n=5
2 Correct 13 ms 23920 KB n=100
3 Correct 16 ms 23888 KB n=100
4 Correct 15 ms 23912 KB n=100
5 Correct 13 ms 23884 KB n=100
6 Correct 13 ms 23884 KB n=100
7 Correct 13 ms 23916 KB n=100
8 Correct 13 ms 23836 KB n=100
9 Correct 13 ms 23884 KB n=100
10 Correct 15 ms 23884 KB n=100
11 Correct 14 ms 23884 KB n=100
12 Correct 13 ms 23880 KB n=100
13 Correct 15 ms 23884 KB n=100
14 Correct 14 ms 23820 KB n=100
15 Correct 13 ms 23920 KB n=100
16 Correct 13 ms 23888 KB n=100
17 Correct 13 ms 23884 KB n=100
18 Correct 14 ms 23884 KB n=100
19 Correct 13 ms 23912 KB n=100
20 Correct 13 ms 23884 KB n=100
21 Correct 14 ms 23836 KB n=100
22 Correct 13 ms 23912 KB n=100
23 Correct 13 ms 23920 KB n=100
24 Correct 13 ms 23884 KB n=100
25 Correct 14 ms 23888 KB n=100
26 Correct 13 ms 23912 KB n=12
27 Correct 14 ms 23832 KB n=100
28 Correct 14 ms 23924 KB n=500
29 Correct 14 ms 24012 KB n=500
30 Correct 15 ms 24000 KB n=500
31 Correct 14 ms 23932 KB n=500
32 Correct 16 ms 23936 KB n=500
33 Correct 15 ms 23956 KB n=500
34 Correct 14 ms 23964 KB n=500
35 Correct 14 ms 24052 KB n=500
36 Correct 14 ms 23924 KB n=500
37 Correct 14 ms 24024 KB n=500
38 Correct 15 ms 24012 KB n=500
39 Correct 14 ms 24012 KB n=500
40 Correct 14 ms 24008 KB n=500
41 Correct 14 ms 23936 KB n=500
42 Correct 15 ms 24012 KB n=500
43 Correct 14 ms 23920 KB n=500
44 Correct 16 ms 24012 KB n=500
45 Correct 14 ms 23920 KB n=500
46 Correct 14 ms 24088 KB n=500
47 Correct 14 ms 23984 KB n=500
48 Correct 14 ms 23928 KB n=500
49 Correct 14 ms 24012 KB n=500
50 Correct 14 ms 23956 KB n=500
51 Correct 14 ms 23964 KB n=500
52 Correct 14 ms 24012 KB n=500
53 Correct 14 ms 24012 KB n=500
54 Correct 14 ms 24028 KB n=500
55 Correct 13 ms 23884 KB n=278
56 Correct 14 ms 23976 KB n=500
57 Correct 14 ms 24012 KB n=500
58 Correct 14 ms 24012 KB n=500
59 Correct 19 ms 24268 KB n=2000
60 Correct 17 ms 24432 KB n=2000
61 Correct 17 ms 24444 KB n=2000
62 Correct 17 ms 24396 KB n=2000
63 Correct 18 ms 24440 KB n=2000
64 Correct 18 ms 24396 KB n=2000
65 Correct 18 ms 24276 KB n=2000
66 Correct 17 ms 24396 KB n=2000
67 Correct 18 ms 24268 KB n=2000
68 Correct 18 ms 24396 KB n=2000
69 Correct 17 ms 24268 KB n=2000
70 Correct 16 ms 24396 KB n=2000
71 Correct 16 ms 24308 KB n=2000
72 Correct 16 ms 24400 KB n=2000
73 Correct 17 ms 24372 KB n=2000
74 Correct 17 ms 24356 KB n=1844
75 Correct 17 ms 24268 KB n=2000
76 Correct 18 ms 24444 KB n=2000
77 Correct 17 ms 24312 KB n=2000
78 Correct 18 ms 24268 KB n=2000
79 Correct 17 ms 24268 KB n=2000
80 Correct 17 ms 24568 KB n=2000
81 Correct 17 ms 24396 KB n=2000
82 Correct 17 ms 24268 KB n=2000
83 Correct 18 ms 24436 KB n=2000
84 Correct 18 ms 24364 KB n=2000
85 Correct 18 ms 24312 KB n=2000
86 Correct 21 ms 24332 KB n=2000
87 Correct 17 ms 24396 KB n=2000
88 Correct 18 ms 24500 KB n=2000
89 Correct 17 ms 24524 KB n=2000
90 Correct 17 ms 24396 KB n=2000
91 Correct 16 ms 24272 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23884 KB n=5
2 Correct 13 ms 23920 KB n=100
3 Correct 16 ms 23888 KB n=100
4 Correct 15 ms 23912 KB n=100
5 Correct 13 ms 23884 KB n=100
6 Correct 13 ms 23884 KB n=100
7 Correct 13 ms 23916 KB n=100
8 Correct 13 ms 23836 KB n=100
9 Correct 13 ms 23884 KB n=100
10 Correct 15 ms 23884 KB n=100
11 Correct 14 ms 23884 KB n=100
12 Correct 13 ms 23880 KB n=100
13 Correct 15 ms 23884 KB n=100
14 Correct 14 ms 23820 KB n=100
15 Correct 13 ms 23920 KB n=100
16 Correct 13 ms 23888 KB n=100
17 Correct 13 ms 23884 KB n=100
18 Correct 14 ms 23884 KB n=100
19 Correct 13 ms 23912 KB n=100
20 Correct 13 ms 23884 KB n=100
21 Correct 14 ms 23836 KB n=100
22 Correct 13 ms 23912 KB n=100
23 Correct 13 ms 23920 KB n=100
24 Correct 13 ms 23884 KB n=100
25 Correct 14 ms 23888 KB n=100
26 Correct 13 ms 23912 KB n=12
27 Correct 14 ms 23832 KB n=100
28 Correct 14 ms 23924 KB n=500
29 Correct 14 ms 24012 KB n=500
30 Correct 15 ms 24000 KB n=500
31 Correct 14 ms 23932 KB n=500
32 Correct 16 ms 23936 KB n=500
33 Correct 15 ms 23956 KB n=500
34 Correct 14 ms 23964 KB n=500
35 Correct 14 ms 24052 KB n=500
36 Correct 14 ms 23924 KB n=500
37 Correct 14 ms 24024 KB n=500
38 Correct 15 ms 24012 KB n=500
39 Correct 14 ms 24012 KB n=500
40 Correct 14 ms 24008 KB n=500
41 Correct 14 ms 23936 KB n=500
42 Correct 15 ms 24012 KB n=500
43 Correct 14 ms 23920 KB n=500
44 Correct 16 ms 24012 KB n=500
45 Correct 14 ms 23920 KB n=500
46 Correct 14 ms 24088 KB n=500
47 Correct 14 ms 23984 KB n=500
48 Correct 14 ms 23928 KB n=500
49 Correct 14 ms 24012 KB n=500
50 Correct 14 ms 23956 KB n=500
51 Correct 14 ms 23964 KB n=500
52 Correct 14 ms 24012 KB n=500
53 Correct 14 ms 24012 KB n=500
54 Correct 14 ms 24028 KB n=500
55 Correct 13 ms 23884 KB n=278
56 Correct 14 ms 23976 KB n=500
57 Correct 14 ms 24012 KB n=500
58 Correct 14 ms 24012 KB n=500
59 Correct 19 ms 24268 KB n=2000
60 Correct 17 ms 24432 KB n=2000
61 Correct 17 ms 24444 KB n=2000
62 Correct 17 ms 24396 KB n=2000
63 Correct 18 ms 24440 KB n=2000
64 Correct 18 ms 24396 KB n=2000
65 Correct 18 ms 24276 KB n=2000
66 Correct 17 ms 24396 KB n=2000
67 Correct 18 ms 24268 KB n=2000
68 Correct 18 ms 24396 KB n=2000
69 Correct 17 ms 24268 KB n=2000
70 Correct 16 ms 24396 KB n=2000
71 Correct 16 ms 24308 KB n=2000
72 Correct 16 ms 24400 KB n=2000
73 Correct 17 ms 24372 KB n=2000
74 Correct 17 ms 24356 KB n=1844
75 Correct 17 ms 24268 KB n=2000
76 Correct 18 ms 24444 KB n=2000
77 Correct 17 ms 24312 KB n=2000
78 Correct 18 ms 24268 KB n=2000
79 Correct 17 ms 24268 KB n=2000
80 Correct 17 ms 24568 KB n=2000
81 Correct 17 ms 24396 KB n=2000
82 Correct 17 ms 24268 KB n=2000
83 Correct 18 ms 24436 KB n=2000
84 Correct 18 ms 24364 KB n=2000
85 Correct 18 ms 24312 KB n=2000
86 Correct 21 ms 24332 KB n=2000
87 Correct 17 ms 24396 KB n=2000
88 Correct 18 ms 24500 KB n=2000
89 Correct 17 ms 24524 KB n=2000
90 Correct 17 ms 24396 KB n=2000
91 Correct 16 ms 24272 KB n=2000
92 Correct 1191 ms 74520 KB n=200000
93 Correct 1354 ms 81012 KB n=200000
94 Correct 1279 ms 85456 KB n=200000
95 Correct 1111 ms 74400 KB n=200000
96 Correct 1119 ms 74408 KB n=200000
97 Correct 1413 ms 79900 KB n=200000
98 Correct 1120 ms 74380 KB n=200000
99 Correct 1343 ms 74504 KB n=200000
100 Correct 1139 ms 74348 KB n=200000
101 Correct 1262 ms 87092 KB n=200000
102 Correct 635 ms 75588 KB n=200000
103 Correct 694 ms 75488 KB n=200000
104 Correct 636 ms 75564 KB n=200000
105 Correct 624 ms 75872 KB n=200000
106 Correct 630 ms 75936 KB n=200000
107 Correct 637 ms 75844 KB n=200000
108 Correct 1286 ms 74528 KB n=200000
109 Correct 1278 ms 74444 KB n=200000
110 Correct 1262 ms 74424 KB n=200000
111 Correct 1148 ms 73976 KB n=200000
112 Correct 1253 ms 85860 KB n=200000
113 Correct 1371 ms 79720 KB n=200000
114 Correct 1139 ms 74104 KB n=200000
115 Correct 1512 ms 77136 KB n=200000
116 Correct 1032 ms 74624 KB n=200000
117 Correct 1211 ms 86428 KB n=200000
118 Correct 1392 ms 78172 KB n=200000
119 Correct 1028 ms 74420 KB n=200000
120 Correct 1203 ms 86116 KB n=200000
121 Correct 1203 ms 86244 KB n=200000
122 Correct 1150 ms 86336 KB n=200000
123 Correct 708 ms 75720 KB n=200000
124 Correct 246 ms 39116 KB n=25264