oj.uz

Submission #1060737

# Submission time Handle Problem Language Result Execution time Memory
1060737 2024-08-15T21:32:45 Z MilosMilutinovic The Ties That Guide Us (CEOI23_incursion) C++17
60 / 100
 293 ms 16316 KB 
#include "incursion.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> mark(vector<pair<int, int>> e, int safe) {
  --safe;
  int n = (int) e.size() + 1;
  vector<vector<int>> g(n);
  for (int i = 0; i + 1 < n; i++) {
    --e[i].first; --e[i].second;
    g[e[i].first].push_back(e[i].second);
    g[e[i].second].push_back(e[i].first);
  }
  int root;
  {
    vector<int> sz(n);
    function<void(int, int)> Dfs = [&](int v, int pv) {
      sz[v] = 1;
      for (int u : g[v]) {
        if (u == pv) {
          continue;
        }
        Dfs(u, v);
        sz[v] += sz[u];
      }
    };
    Dfs(0, 0);
    vector<int> cen;
    function<int(int, int)> FindCentroid = [&](int v, int pv) {
      if (sz[v] * 2 == n) {
        cen.push_back(pv);
      }
      for (int u : g[v]) {
        if (u == pv || sz[u] * 2 < n) {
          continue;
        }
        return FindCentroid(u, v);
      }
      cen.push_back(v);
      return v;
    };
    root = FindCentroid(0, 0);
    if ((int) cen.size() == 2) {
      vector<int> que(1, safe);
      vector<bool> was(n);
      was[safe] = true;
      for (int b = 0; b < (int) que.size(); b++) {
        int i = que[b];
        if (i == cen[0] || i == cen[1]) {
          root = i;
          break;
        }
        for (int j : g[i]) {
          if (!was[j]) {
            que.push_back(j);
            was[j] = true;
          }
        }
      }
    }
  }
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    if ((int) g[i].size() == 2) {
      cnt += 1;
    }
  }
  if (cnt == 1) {
    for (int i = 0; i < n; i++) {
      if ((int) g[i].size() == 2) {
        root = i;
      }
    }
  }
  vector<int> dfn(n);
  vector<int> dfo(n);
  int T = -1;
  function<void(int, int)> Dfs = [&](int v, int pv) {
    dfn[v] = ++T;
    for (int u : g[v]) {
      if (u == pv) {
        continue;
      }
      Dfs(u, v);
    }
    dfo[v] = T;
  };
  Dfs(root, root);
  vector<int> seq(n);
  for (int i = 0; i < n; i++) {
    if (dfn[i] <= dfn[safe] && dfo[safe] <= dfo[i]) {
      seq[i] = 1;
    } else {
      seq[i] = 0;
    }
  }
  return seq;
}

void locate(vector<pair<int, int>> e, int curr, int t) {
  --curr;
  int n = (int) e.size() + 1;
  vector<vector<int>> g(n);
  for (int i = 0; i + 1 < n; i++) {
    --e[i].first; --e[i].second;
    g[e[i].first].push_back(e[i].second);
    g[e[i].second].push_back(e[i].first);
  }
  vector<int> cen;
  {
    vector<int> sz(n);
    function<void(int, int)> Dfs = [&](int v, int pv) {
      sz[v] = 1;
      for (int u : g[v]) {
        if (u == pv) {
          continue;
        }
        Dfs(u, v);
        sz[v] += sz[u];
      }
    };
    Dfs(0, 0);
    function<void(int, int)> Find = [&](int v, int pv) {
      if (sz[v] * 2 == n) {
        cen.push_back(pv);
      }
      for (int u : g[v]) {
        if (u == pv || sz[u] * 2 < n) {
          continue;
        }
        Find(u, v);
        return;
      }
      cen.push_back(v);
    };
    Find(0, 0);
  }
  int root = cen[0];
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    if ((int) g[i].size() == 2) {
      cnt += 1;
    }
  }
  if (cnt == 1) {
    for (int i = 0; i < n; i++) {
      if ((int) g[i].size() == 2) {
        root = i;
      }
    }
  }
  vector<int> x(n, -1);
  vector<int> pr(n);
  vector<int> sz(n);
  function<void(int, int)> Dfs = [&](int v, int pv) {
    pr[v] = pv;
    sz[v] = 1;
    for (int u : g[v]) {
      if (u == pv) {
        continue;
      }
      Dfs(u, v);
      sz[v] += sz[u];
      if (x[v] == -1 || sz[x[v]] < sz[u]) {
        x[v] = u;
      }
    }
  };
  Dfs(root, root);
  while (true) {
    if (curr == root && t == 0) {
      root = cen[1];
      x = vector<int>(n, -1);
      Dfs(root, root);
      t = visit(root + 1);
      assert(t == 1);
      curr = root;
      continue;
    }
    if (t == 0) {
      t = visit(pr[curr] + 1);
      curr = pr[curr];
      continue;
    }
    if (x[curr] == -1) {
      return;
    }
    int k = visit(x[curr] + 1);
    if (k == 1) {
      curr = x[curr];
      t = k;
      continue;
    }
    visit(curr + 1);
    bool found = false;
    for (int u : g[curr]) {
      if (u == pr[curr] || u == x[curr]) {
        continue;
      }
      int k = visit(u + 1);
      if (k == 1) {
        t = k;
        curr = u;
        found = true;
        break;
      }
      visit(curr + 1);
    }
    if (!found) {
      return;
    }
  }
}

Compilation message

interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         int l = (numbers.size() == N ? N : 0);
      |                  ~~~~~~~~~~~~~~~^~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 768 KB Correct

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 13336 KB Correct
2 Correct 192 ms 13740 KB Correct
3 Correct 113 ms 14584 KB Correct
4 Correct 110 ms 15508 KB Correct
5 Correct 193 ms 15316 KB Correct
6 Correct 91 ms 15356 KB Correct
7 Correct 90 ms 13372 KB Correct
8 Correct 223 ms 14080 KB Correct
9 Correct 201 ms 14720 KB Correct
10 Correct 144 ms 13772 KB Correct
11 Correct 103 ms 15680 KB Correct
12 Correct 260 ms 13824 KB Correct
13 Correct 92 ms 13188 KB Correct
14 Correct 92 ms 13808 KB Correct
15 Correct 207 ms 15024 KB Correct
16 Correct 225 ms 15936 KB Correct
17 Correct 141 ms 12852 KB Correct
18 Correct 110 ms 13548 KB Correct
19 Correct 164 ms 13124 KB Correct
20 Correct 86 ms 15272 KB Correct
21 Correct 90 ms 14068 KB Correct
22 Correct 231 ms 14096 KB Correct
23 Correct 214 ms 14060 KB Correct
24 Correct 110 ms 13376 KB Correct
25 Correct 100 ms 14992 KB Correct
26 Correct 92 ms 13220 KB Correct
27 Correct 86 ms 13816 KB Correct
28 Correct 89 ms 14332 KB Correct
29 Correct 216 ms 14456 KB Correct
30 Correct 219 ms 13072 KB Correct
31 Correct 92 ms 15424 KB Correct
32 Correct 272 ms 14560 KB Correct
33 Correct 224 ms 14816 KB Correct
34 Correct 83 ms 13316 KB Correct
35 Correct 78 ms 12880 KB Correct
36 Correct 242 ms 14592 KB Correct
37 Correct 217 ms 14328 KB Correct
38 Correct 269 ms 15308 KB Correct
39 Correct 147 ms 15592 KB Correct
40 Correct 198 ms 15276 KB Correct
41 Correct 93 ms 14640 KB Correct
42 Correct 87 ms 14404 KB Correct
43 Correct 213 ms 14352 KB Correct
44 Correct 229 ms 12592 KB Correct
45 Correct 90 ms 13320 KB Correct
46 Correct 95 ms 13984 KB Correct
47 Correct 91 ms 14696 KB Correct
48 Correct 88 ms 13048 KB Correct
49 Correct 91 ms 15168 KB Correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 7944 KB Correct
2 Correct 81 ms 8172 KB Correct
3 Correct 79 ms 8008 KB Correct
4 Correct 96 ms 12256 KB Correct
5 Correct 158 ms 12448 KB Correct
6 Correct 182 ms 12284 KB Correct
7 Correct 79 ms 7944 KB Correct
8 Correct 81 ms 7920 KB Correct
9 Correct 76 ms 7752 KB Correct
10 Correct 77 ms 8004 KB Correct
11 Correct 77 ms 8052 KB Correct
12 Correct 83 ms 8004 KB Correct
13 Correct 78 ms 8016 KB Correct
14 Correct 61 ms 6140 KB Correct
15 Correct 62 ms 5884 KB Correct
16 Correct 75 ms 7932 KB Correct
17 Correct 78 ms 7864 KB Correct
18 Correct 78 ms 8012 KB Correct
19 Correct 76 ms 7928 KB Correct
20 Correct 63 ms 6140 KB Correct
21 Correct 54 ms 6296 KB Correct
22 Correct 63 ms 6140 KB Correct
23 Correct 62 ms 6220 KB Correct
24 Correct 53 ms 6288 KB Correct
25 Correct 57 ms 6120 KB Correct
26 Correct 78 ms 8140 KB Correct
27 Correct 84 ms 8116 KB Correct
28 Correct 81 ms 7992 KB Correct
29 Correct 79 ms 7920 KB Correct
30 Correct 84 ms 7932 KB Correct
31 Correct 79 ms 8048 KB Correct
32 Correct 80 ms 8000 KB Correct
33 Correct 78 ms 8000 KB Correct
34 Correct 81 ms 8000 KB Correct
35 Correct 88 ms 7996 KB Correct
36 Correct 92 ms 8032 KB Correct
37 Correct 82 ms 7936 KB Correct
38 Correct 82 ms 7924 KB Correct
39 Correct 67 ms 7932 KB Correct
40 Correct 84 ms 8136 KB Correct
41 Correct 79 ms 7916 KB Correct
42 Correct 86 ms 7860 KB Correct
43 Correct 78 ms 7928 KB Correct
44 Correct 78 ms 8000 KB Correct
45 Correct 87 ms 7912 KB Correct
46 Correct 84 ms 8128 KB Correct
47 Correct 81 ms 8004 KB Correct
48 Correct 80 ms 7916 KB Correct
49 Correct 86 ms 7920 KB Correct
50 Correct 80 ms 8260 KB Correct
51 Correct 92 ms 8000 KB Correct
52 Correct 81 ms 7928 KB Correct
53 Correct 79 ms 7996 KB Correct
54 Correct 80 ms 8212 KB Correct
55 Correct 90 ms 8088 KB Correct
56 Correct 80 ms 8372 KB Correct
57 Correct 76 ms 8180 KB Correct
58 Correct 87 ms 8316 KB Correct
59 Correct 80 ms 8508 KB Correct
60 Correct 79 ms 7972 KB Correct
61 Correct 84 ms 8520 KB Correct
62 Correct 81 ms 8512 KB Correct
63 Correct 82 ms 8440 KB Correct
64 Correct 81 ms 8364 KB Correct
65 Correct 81 ms 8376 KB Correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 768 KB Correct
2 Correct 206 ms 13336 KB Correct
3 Correct 192 ms 13740 KB Correct
4 Correct 113 ms 14584 KB Correct
5 Correct 110 ms 15508 KB Correct
6 Correct 193 ms 15316 KB Correct
7 Correct 91 ms 15356 KB Correct
8 Correct 90 ms 13372 KB Correct
9 Correct 223 ms 14080 KB Correct
10 Correct 201 ms 14720 KB Correct
11 Correct 144 ms 13772 KB Correct
12 Correct 103 ms 15680 KB Correct
13 Correct 260 ms 13824 KB Correct
14 Correct 92 ms 13188 KB Correct
15 Correct 92 ms 13808 KB Correct
16 Correct 207 ms 15024 KB Correct
17 Correct 225 ms 15936 KB Correct
18 Correct 141 ms 12852 KB Correct
19 Correct 110 ms 13548 KB Correct
20 Correct 164 ms 13124 KB Correct
21 Correct 86 ms 15272 KB Correct
22 Correct 90 ms 14068 KB Correct
23 Correct 231 ms 14096 KB Correct
24 Correct 214 ms 14060 KB Correct
25 Correct 110 ms 13376 KB Correct
26 Correct 100 ms 14992 KB Correct
27 Correct 92 ms 13220 KB Correct
28 Correct 86 ms 13816 KB Correct
29 Correct 89 ms 14332 KB Correct
30 Correct 216 ms 14456 KB Correct
31 Correct 219 ms 13072 KB Correct
32 Correct 92 ms 15424 KB Correct
33 Correct 272 ms 14560 KB Correct
34 Correct 224 ms 14816 KB Correct
35 Correct 83 ms 13316 KB Correct
36 Correct 78 ms 12880 KB Correct
37 Correct 242 ms 14592 KB Correct
38 Correct 217 ms 14328 KB Correct
39 Correct 269 ms 15308 KB Correct
40 Correct 147 ms 15592 KB Correct
41 Correct 198 ms 15276 KB Correct
42 Correct 93 ms 14640 KB Correct
43 Correct 87 ms 14404 KB Correct
44 Correct 213 ms 14352 KB Correct
45 Correct 229 ms 12592 KB Correct
46 Correct 90 ms 13320 KB Correct
47 Correct 95 ms 13984 KB Correct
48 Correct 91 ms 14696 KB Correct
49 Correct 88 ms 13048 KB Correct
50 Correct 91 ms 15168 KB Correct
51 Correct 82 ms 7944 KB Correct
52 Correct 81 ms 8172 KB Correct
53 Correct 79 ms 8008 KB Correct
54 Correct 96 ms 12256 KB Correct
55 Correct 158 ms 12448 KB Correct
56 Correct 182 ms 12284 KB Correct
57 Correct 79 ms 7944 KB Correct
58 Correct 81 ms 7920 KB Correct
59 Correct 76 ms 7752 KB Correct
60 Correct 77 ms 8004 KB Correct
61 Correct 77 ms 8052 KB Correct
62 Correct 83 ms 8004 KB Correct
63 Correct 78 ms 8016 KB Correct
64 Correct 61 ms 6140 KB Correct
65 Correct 62 ms 5884 KB Correct
66 Correct 75 ms 7932 KB Correct
67 Correct 78 ms 7864 KB Correct
68 Correct 78 ms 8012 KB Correct
69 Correct 76 ms 7928 KB Correct
70 Correct 63 ms 6140 KB Correct
71 Correct 54 ms 6296 KB Correct
72 Correct 63 ms 6140 KB Correct
73 Correct 62 ms 6220 KB Correct
74 Correct 53 ms 6288 KB Correct
75 Correct 57 ms 6120 KB Correct
76 Correct 78 ms 8140 KB Correct
77 Correct 84 ms 8116 KB Correct
78 Correct 81 ms 7992 KB Correct
79 Correct 79 ms 7920 KB Correct
80 Correct 84 ms 7932 KB Correct
81 Correct 79 ms 8048 KB Correct
82 Correct 80 ms 8000 KB Correct
83 Correct 78 ms 8000 KB Correct
84 Correct 81 ms 8000 KB Correct
85 Correct 88 ms 7996 KB Correct
86 Correct 92 ms 8032 KB Correct
87 Correct 82 ms 7936 KB Correct
88 Correct 82 ms 7924 KB Correct
89 Correct 67 ms 7932 KB Correct
90 Correct 84 ms 8136 KB Correct
91 Correct 79 ms 7916 KB Correct
92 Correct 86 ms 7860 KB Correct
93 Correct 78 ms 7928 KB Correct
94 Correct 78 ms 8000 KB Correct
95 Correct 87 ms 7912 KB Correct
96 Correct 84 ms 8128 KB Correct
97 Correct 81 ms 8004 KB Correct
98 Correct 80 ms 7916 KB Correct
99 Correct 86 ms 7920 KB Correct
100 Correct 80 ms 8260 KB Correct
101 Correct 92 ms 8000 KB Correct
102 Correct 81 ms 7928 KB Correct
103 Correct 79 ms 7996 KB Correct
104 Correct 80 ms 8212 KB Correct
105 Correct 90 ms 8088 KB Correct
106 Correct 80 ms 8372 KB Correct
107 Correct 76 ms 8180 KB Correct
108 Correct 87 ms 8316 KB Correct
109 Correct 80 ms 8508 KB Correct
110 Correct 79 ms 7972 KB Correct
111 Correct 84 ms 8520 KB Correct
112 Correct 81 ms 8512 KB Correct
113 Correct 82 ms 8440 KB Correct
114 Correct 81 ms 8364 KB Correct
115 Correct 81 ms 8376 KB Correct
116 Correct 87 ms 8188 KB Correct
117 Correct 81 ms 8444 KB Correct
118 Correct 89 ms 8036 KB Correct
119 Correct 83 ms 7952 KB Correct
120 Correct 87 ms 8112 KB Correct
121 Correct 86 ms 8700 KB Correct
122 Correct 83 ms 7880 KB Correct
123 Correct 89 ms 12284 KB Correct
124 Correct 144 ms 12296 KB Correct
125 Correct 179 ms 12220 KB Correct
126 Correct 76 ms 8008 KB Correct
127 Correct 70 ms 7924 KB Correct
128 Correct 75 ms 8008 KB Correct
129 Correct 83 ms 7760 KB Correct
130 Correct 76 ms 7912 KB Correct
131 Correct 86 ms 7760 KB Correct
132 Correct 87 ms 7932 KB Correct
133 Correct 61 ms 6136 KB Correct
134 Correct 57 ms 6144 KB Correct
135 Correct 77 ms 7916 KB Correct
136 Correct 77 ms 8004 KB Correct
137 Correct 80 ms 7860 KB Correct
138 Correct 79 ms 7852 KB Correct
139 Correct 54 ms 6044 KB Correct
140 Correct 72 ms 6136 KB Correct
141 Correct 51 ms 5876 KB Correct
142 Correct 61 ms 6128 KB Correct
143 Correct 59 ms 6124 KB Correct
144 Correct 55 ms 6040 KB Correct
145 Correct 73 ms 7832 KB Correct
146 Correct 81 ms 7916 KB Correct
147 Correct 75 ms 8004 KB Correct
148 Correct 90 ms 8004 KB Correct
149 Correct 81 ms 8124 KB Correct
150 Correct 90 ms 7920 KB Correct
151 Correct 82 ms 7920 KB Correct
152 Correct 78 ms 7996 KB Correct
153 Correct 92 ms 8200 KB Correct
154 Correct 82 ms 7912 KB Correct
155 Correct 81 ms 8004 KB Correct
156 Correct 77 ms 7996 KB Correct
157 Correct 78 ms 7932 KB Correct
158 Correct 80 ms 7928 KB Correct
159 Correct 78 ms 7936 KB Correct
160 Correct 84 ms 8000 KB Correct
161 Correct 68 ms 7996 KB Correct
162 Correct 80 ms 7944 KB Correct
163 Correct 87 ms 8260 KB Correct
164 Correct 81 ms 7912 KB Correct
165 Correct 81 ms 7864 KB Correct
166 Correct 84 ms 8004 KB Correct
167 Correct 79 ms 8000 KB Correct
168 Correct 77 ms 7988 KB Correct
169 Correct 78 ms 8004 KB Correct
170 Correct 76 ms 8108 KB Correct
171 Correct 94 ms 7860 KB Correct
172 Correct 86 ms 7840 KB Correct
173 Correct 80 ms 8176 KB Correct
174 Correct 74 ms 7924 KB Correct
175 Correct 75 ms 8424 KB Correct
176 Correct 75 ms 8376 KB Correct
177 Correct 79 ms 8504 KB Correct
178 Correct 91 ms 8528 KB Correct
179 Correct 82 ms 8184 KB Correct
180 Correct 81 ms 8268 KB Correct
181 Correct 73 ms 8436 KB Correct
182 Correct 83 ms 8632 KB Correct
183 Correct 78 ms 8004 KB Correct
184 Correct 76 ms 8192 KB Correct
185 Correct 227 ms 13408 KB Correct
186 Correct 216 ms 13800 KB Correct
187 Correct 118 ms 14908 KB Correct
188 Correct 111 ms 15352 KB Correct
189 Correct 196 ms 15240 KB Correct
190 Correct 95 ms 15624 KB Correct
191 Correct 86 ms 13452 KB Correct
192 Correct 209 ms 14144 KB Correct
193 Correct 225 ms 14836 KB Correct
194 Correct 158 ms 14000 KB Correct
195 Correct 99 ms 15752 KB Correct
196 Correct 293 ms 14108 KB Correct
197 Correct 87 ms 13108 KB Correct
198 Correct 81 ms 13820 KB Correct
199 Correct 231 ms 14752 KB Correct
200 Correct 215 ms 16316 KB Correct
201 Correct 110 ms 12784 KB Correct
202 Correct 102 ms 13408 KB Correct
203 Correct 175 ms 13036 KB Correct
204 Correct 98 ms 15168 KB Correct
205 Correct 87 ms 14084 KB Correct
206 Correct 221 ms 13936 KB Correct
207 Correct 218 ms 14180 KB Correct
208 Correct 93 ms 13740 KB Correct
209 Correct 90 ms 14748 KB Correct
210 Correct 90 ms 13228 KB Correct
211 Correct 93 ms 13824 KB Correct
212 Correct 89 ms 14400 KB Correct
213 Correct 216 ms 14208 KB Correct
214 Correct 221 ms 13008 KB Correct
215 Correct 100 ms 15424 KB Correct
216 Correct 250 ms 14616 KB Correct
217 Correct 260 ms 14808 KB Correct
218 Correct 86 ms 13436 KB Correct
219 Correct 86 ms 13052 KB Correct
220 Correct 231 ms 14140 KB Correct
221 Correct 209 ms 14332 KB Correct
222 Correct 259 ms 15304 KB Correct
223 Correct 145 ms 15328 KB Correct
224 Correct 206 ms 15256 KB Correct
225 Correct 86 ms 14652 KB Correct
226 Correct 89 ms 14452 KB Correct
227 Correct 200 ms 14356 KB Correct
228 Correct 180 ms 12792 KB Correct
229 Correct 94 ms 13292 KB Correct
230 Correct 93 ms 13796 KB Correct
231 Correct 98 ms 14572 KB Correct
232 Correct 90 ms 12800 KB Correct
233 Correct 79 ms 15240 KB Correct
234 Correct 94 ms 11472 KB Correct
235 Correct 97 ms 11452 KB Correct
236 Correct 62 ms 6128 KB Correct
237 Correct 55 ms 6384 KB Correct
238 Correct 60 ms 6232 KB Correct
239 Correct 37 ms 4804 KB Correct
240 Incorrect 80 ms 8000 KB Not correct
241 Halted 0 ms 0 KB -