oj.uz

Submission #44005

# Submission time Handle Problem Language Result Execution time Memory
44005 2018-03-29T10:30:13 Z Nordway Birthday gift (IZhO18_treearray) C++14
30 / 100
 4000 ms 26852 KB 
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string.h>
#include <stdio.h>
#include <assert.h>

using namespace std;

typedef long long LL;
typedef map<string , int> MSI;
typedef vector<int> VI;
typedef pair<int, int> PII;

#define endl '\n'
#define pb(x) push_back(x)
#define sqr(x) ((x) * (x))
#define F first
#define S second
#define SZ(t) ((int) t.size())
#define len(t) ((int) t.length())
#define base LL(1e9 + 7)
#define fname ""
#define sz 1000 * 1000
#define EPS (1e-8)
#define INF ((int)1e9 + 9)
#define mp make_pair

int tin[sz], T, tout[sz], n, k, q, b[sz], p[sz];
VI a[sz];

bool upper(int v, int u) {
  return tin[v] <= tin[u] && tout[u] <= tout[v];
}

void dfs(int v, int pr = 0) {
  tin[v] = ++T;
  p[v] = pr;
  for (int i = 0; i < a[v].size(); i++) {
    int to = a[v][i];
    if (to == pr) continue;
    dfs(to, v);
  }
  tout[v] = ++T;
}

int main()
{
//    freopen(fname"in", "r", stdin);
//    freopen(fname"out", "w", stdout);

  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cin >> n >> k >> q;
  for (int i = 2; i <= n; i++) {
    int v, u;
    cin >> v >> u;
    a[v].pb(u);
    a[u].pb(v);
  }

  for (int i = 1; i <= k; i++) {
    cin >> b[i];
  }
  dfs(1);
  tout[0] = 1e9;

  int l, r, x, ty;
  for (int i = 1; i <= q; i++) {
    cin >> ty;
    if (ty == 1) {
      cin >> l >> x;
      b[l] = x;
    } else {
      cin >> l >> r >> x;
      int f = 0;
      for (int L = l; !f && L <= r; L++) {
        int cur = b[L];
        for (int R = L; !f && R <= r; R++) {
          while (!upper(cur, b[R])) cur = p[cur];
          if (!upper(x, cur)) break;
          if (cur == x) {
            f = 1;
            cout << L << " " << R << "\n";
          }
        }
      }
      if (!f)
        cout << -1 << " " << -1 << "\n";
    }
  }

}

Compilation message

treearray.cpp: In function 'void dfs(int, int)':
treearray.cpp:56:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a[v].size(); i++) {
                   ~~^~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23928 KB n=5
2 Correct 21 ms 24044 KB n=100
3 Correct 21 ms 24284 KB n=100
4 Correct 21 ms 24284 KB n=100
5 Correct 23 ms 24284 KB n=100
6 Correct 21 ms 24284 KB n=100
7 Correct 21 ms 24284 KB n=100
8 Correct 19 ms 24284 KB n=100
9 Correct 75 ms 24328 KB n=100
10 Correct 23 ms 24344 KB n=100
11 Correct 20 ms 24344 KB n=100
12 Correct 26 ms 24356 KB n=100
13 Correct 22 ms 24412 KB n=100
14 Correct 24 ms 24412 KB n=100
15 Correct 20 ms 24412 KB n=100
16 Correct 22 ms 24412 KB n=100
17 Correct 21 ms 24412 KB n=100
18 Correct 25 ms 24412 KB n=100
19 Correct 23 ms 24412 KB n=100
20 Correct 24 ms 24412 KB n=100
21 Correct 22 ms 24412 KB n=100
22 Correct 21 ms 24412 KB n=100
23 Correct 22 ms 24412 KB n=100
24 Correct 22 ms 24412 KB n=100
25 Correct 22 ms 24412 KB n=100
26 Correct 22 ms 24412 KB n=12
27 Correct 21 ms 24412 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23928 KB n=5
2 Correct 21 ms 24044 KB n=100
3 Correct 21 ms 24284 KB n=100
4 Correct 21 ms 24284 KB n=100
5 Correct 23 ms 24284 KB n=100
6 Correct 21 ms 24284 KB n=100
7 Correct 21 ms 24284 KB n=100
8 Correct 19 ms 24284 KB n=100
9 Correct 75 ms 24328 KB n=100
10 Correct 23 ms 24344 KB n=100
11 Correct 20 ms 24344 KB n=100
12 Correct 26 ms 24356 KB n=100
13 Correct 22 ms 24412 KB n=100
14 Correct 24 ms 24412 KB n=100
15 Correct 20 ms 24412 KB n=100
16 Correct 22 ms 24412 KB n=100
17 Correct 21 ms 24412 KB n=100
18 Correct 25 ms 24412 KB n=100
19 Correct 23 ms 24412 KB n=100
20 Correct 24 ms 24412 KB n=100
21 Correct 22 ms 24412 KB n=100
22 Correct 21 ms 24412 KB n=100
23 Correct 22 ms 24412 KB n=100
24 Correct 22 ms 24412 KB n=100
25 Correct 22 ms 24412 KB n=100
26 Correct 22 ms 24412 KB n=12
27 Correct 21 ms 24412 KB n=100
28 Correct 21 ms 24508 KB n=500
29 Correct 30 ms 24584 KB n=500
30 Correct 26 ms 24584 KB n=500
31 Correct 28 ms 24584 KB n=500
32 Correct 22 ms 24616 KB n=500
33 Correct 25 ms 24628 KB n=500
34 Correct 21 ms 24644 KB n=500
35 Correct 31 ms 24644 KB n=500
36 Correct 24 ms 24644 KB n=500
37 Correct 23 ms 24684 KB n=500
38 Correct 25 ms 24704 KB n=500
39 Correct 23 ms 24712 KB n=500
40 Correct 22 ms 24728 KB n=500
41 Correct 27 ms 24744 KB n=500
42 Correct 21 ms 24760 KB n=500
43 Correct 22 ms 24772 KB n=500
44 Correct 22 ms 24800 KB n=500
45 Correct 22 ms 24812 KB n=500
46 Correct 30 ms 24824 KB n=500
47 Correct 29 ms 24840 KB n=500
48 Correct 20 ms 24856 KB n=500
49 Correct 26 ms 24868 KB n=500
50 Correct 27 ms 24884 KB n=500
51 Correct 25 ms 24896 KB n=500
52 Correct 36 ms 24912 KB n=500
53 Correct 24 ms 24928 KB n=500
54 Correct 42 ms 24948 KB n=500
55 Correct 21 ms 24960 KB n=278
56 Correct 147 ms 25088 KB n=500
57 Correct 164 ms 25088 KB n=500
58 Correct 21 ms 25088 KB n=500

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23928 KB n=5
2 Correct 21 ms 24044 KB n=100
3 Correct 21 ms 24284 KB n=100
4 Correct 21 ms 24284 KB n=100
5 Correct 23 ms 24284 KB n=100
6 Correct 21 ms 24284 KB n=100
7 Correct 21 ms 24284 KB n=100
8 Correct 19 ms 24284 KB n=100
9 Correct 75 ms 24328 KB n=100
10 Correct 23 ms 24344 KB n=100
11 Correct 20 ms 24344 KB n=100
12 Correct 26 ms 24356 KB n=100
13 Correct 22 ms 24412 KB n=100
14 Correct 24 ms 24412 KB n=100
15 Correct 20 ms 24412 KB n=100
16 Correct 22 ms 24412 KB n=100
17 Correct 21 ms 24412 KB n=100
18 Correct 25 ms 24412 KB n=100
19 Correct 23 ms 24412 KB n=100
20 Correct 24 ms 24412 KB n=100
21 Correct 22 ms 24412 KB n=100
22 Correct 21 ms 24412 KB n=100
23 Correct 22 ms 24412 KB n=100
24 Correct 22 ms 24412 KB n=100
25 Correct 22 ms 24412 KB n=100
26 Correct 22 ms 24412 KB n=12
27 Correct 21 ms 24412 KB n=100
28 Correct 21 ms 24508 KB n=500
29 Correct 30 ms 24584 KB n=500
30 Correct 26 ms 24584 KB n=500
31 Correct 28 ms 24584 KB n=500
32 Correct 22 ms 24616 KB n=500
33 Correct 25 ms 24628 KB n=500
34 Correct 21 ms 24644 KB n=500
35 Correct 31 ms 24644 KB n=500
36 Correct 24 ms 24644 KB n=500
37 Correct 23 ms 24684 KB n=500
38 Correct 25 ms 24704 KB n=500
39 Correct 23 ms 24712 KB n=500
40 Correct 22 ms 24728 KB n=500
41 Correct 27 ms 24744 KB n=500
42 Correct 21 ms 24760 KB n=500
43 Correct 22 ms 24772 KB n=500
44 Correct 22 ms 24800 KB n=500
45 Correct 22 ms 24812 KB n=500
46 Correct 30 ms 24824 KB n=500
47 Correct 29 ms 24840 KB n=500
48 Correct 20 ms 24856 KB n=500
49 Correct 26 ms 24868 KB n=500
50 Correct 27 ms 24884 KB n=500
51 Correct 25 ms 24896 KB n=500
52 Correct 36 ms 24912 KB n=500
53 Correct 24 ms 24928 KB n=500
54 Correct 42 ms 24948 KB n=500
55 Correct 21 ms 24960 KB n=278
56 Correct 147 ms 25088 KB n=500
57 Correct 164 ms 25088 KB n=500
58 Correct 21 ms 25088 KB n=500
59 Correct 23 ms 25176 KB n=2000
60 Correct 557 ms 25308 KB n=2000
61 Correct 345 ms 25404 KB n=2000
62 Correct 145 ms 25404 KB n=2000
63 Correct 22 ms 25404 KB n=2000
64 Correct 236 ms 25568 KB n=2000
65 Correct 26 ms 25568 KB n=2000
66 Correct 462 ms 25568 KB n=2000
67 Correct 23 ms 25656 KB n=2000
68 Correct 289 ms 25788 KB n=2000
69 Correct 59 ms 25788 KB n=2000
70 Correct 59 ms 25788 KB n=2000
71 Correct 61 ms 25788 KB n=2000
72 Correct 42 ms 25872 KB n=2000
73 Correct 42 ms 25928 KB n=2000
74 Correct 27 ms 25984 KB n=1844
75 Correct 42 ms 26032 KB n=2000
76 Correct 40 ms 26088 KB n=2000
77 Correct 40 ms 26140 KB n=2000
78 Correct 43 ms 26192 KB n=2000
79 Correct 24 ms 26244 KB n=2000
80 Correct 405 ms 26420 KB n=2000
81 Correct 227 ms 26480 KB n=2000
82 Correct 26 ms 26480 KB n=2000
83 Correct 352 ms 26584 KB n=2000
84 Correct 35 ms 26584 KB n=2000
85 Correct 179 ms 26584 KB n=2000
86 Correct 105 ms 26644 KB n=2000
87 Correct 26 ms 26672 KB n=2000
88 Execution timed out 4041 ms 26852 KB Time limit exceeded
89 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23928 KB n=5
2 Correct 21 ms 24044 KB n=100
3 Correct 21 ms 24284 KB n=100
4 Correct 21 ms 24284 KB n=100
5 Correct 23 ms 24284 KB n=100
6 Correct 21 ms 24284 KB n=100
7 Correct 21 ms 24284 KB n=100
8 Correct 19 ms 24284 KB n=100
9 Correct 75 ms 24328 KB n=100
10 Correct 23 ms 24344 KB n=100
11 Correct 20 ms 24344 KB n=100
12 Correct 26 ms 24356 KB n=100
13 Correct 22 ms 24412 KB n=100
14 Correct 24 ms 24412 KB n=100
15 Correct 20 ms 24412 KB n=100
16 Correct 22 ms 24412 KB n=100
17 Correct 21 ms 24412 KB n=100
18 Correct 25 ms 24412 KB n=100
19 Correct 23 ms 24412 KB n=100
20 Correct 24 ms 24412 KB n=100
21 Correct 22 ms 24412 KB n=100
22 Correct 21 ms 24412 KB n=100
23 Correct 22 ms 24412 KB n=100
24 Correct 22 ms 24412 KB n=100
25 Correct 22 ms 24412 KB n=100
26 Correct 22 ms 24412 KB n=12
27 Correct 21 ms 24412 KB n=100
28 Correct 21 ms 24508 KB n=500
29 Correct 30 ms 24584 KB n=500
30 Correct 26 ms 24584 KB n=500
31 Correct 28 ms 24584 KB n=500
32 Correct 22 ms 24616 KB n=500
33 Correct 25 ms 24628 KB n=500
34 Correct 21 ms 24644 KB n=500
35 Correct 31 ms 24644 KB n=500
36 Correct 24 ms 24644 KB n=500
37 Correct 23 ms 24684 KB n=500
38 Correct 25 ms 24704 KB n=500
39 Correct 23 ms 24712 KB n=500
40 Correct 22 ms 24728 KB n=500
41 Correct 27 ms 24744 KB n=500
42 Correct 21 ms 24760 KB n=500
43 Correct 22 ms 24772 KB n=500
44 Correct 22 ms 24800 KB n=500
45 Correct 22 ms 24812 KB n=500
46 Correct 30 ms 24824 KB n=500
47 Correct 29 ms 24840 KB n=500
48 Correct 20 ms 24856 KB n=500
49 Correct 26 ms 24868 KB n=500
50 Correct 27 ms 24884 KB n=500
51 Correct 25 ms 24896 KB n=500
52 Correct 36 ms 24912 KB n=500
53 Correct 24 ms 24928 KB n=500
54 Correct 42 ms 24948 KB n=500
55 Correct 21 ms 24960 KB n=278
56 Correct 147 ms 25088 KB n=500
57 Correct 164 ms 25088 KB n=500
58 Correct 21 ms 25088 KB n=500
59 Correct 23 ms 25176 KB n=2000
60 Correct 557 ms 25308 KB n=2000
61 Correct 345 ms 25404 KB n=2000
62 Correct 145 ms 25404 KB n=2000
63 Correct 22 ms 25404 KB n=2000
64 Correct 236 ms 25568 KB n=2000
65 Correct 26 ms 25568 KB n=2000
66 Correct 462 ms 25568 KB n=2000
67 Correct 23 ms 25656 KB n=2000
68 Correct 289 ms 25788 KB n=2000
69 Correct 59 ms 25788 KB n=2000
70 Correct 59 ms 25788 KB n=2000
71 Correct 61 ms 25788 KB n=2000
72 Correct 42 ms 25872 KB n=2000
73 Correct 42 ms 25928 KB n=2000
74 Correct 27 ms 25984 KB n=1844
75 Correct 42 ms 26032 KB n=2000
76 Correct 40 ms 26088 KB n=2000
77 Correct 40 ms 26140 KB n=2000
78 Correct 43 ms 26192 KB n=2000
79 Correct 24 ms 26244 KB n=2000
80 Correct 405 ms 26420 KB n=2000
81 Correct 227 ms 26480 KB n=2000
82 Correct 26 ms 26480 KB n=2000
83 Correct 352 ms 26584 KB n=2000
84 Correct 35 ms 26584 KB n=2000
85 Correct 179 ms 26584 KB n=2000
86 Correct 105 ms 26644 KB n=2000
87 Correct 26 ms 26672 KB n=2000
88 Execution timed out 4041 ms 26852 KB Time limit exceeded
89 Halted 0 ms 0 KB -