oj.uz

Submission #1073413

# Submission time Handle Problem Language Result Execution time Memory
1073413 2024-08-24T14:21:18 Z NeroZein The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 283 ms 17660 KB 
#include "incursion.h"
#include <bits/stdc++.h>
 
using namespace std; 
 
vector<int> mark(vector<pair<int, int>> F, int safe) {
  int n = (int) F.size() + 1; 
  vector<vector<int>> g(n);
  for (int i = 0; i < n - 1; ++i) {
    auto [u, v] = F[i];
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u); 
  }
  vector<int> sz(n); 
  vector<int> dist(n);
  vector<int> ties(n);
  function<void(int, int)> dfs = [&](int v, int p) {
    sz[v] = 1;
    for (int u : g[v]) {
      if (u == p) {
        continue; 
      }
      dist[u] = dist[v] + 1; 
      dfs(u, v);
      sz[v] += sz[u];
    }
  };
  --safe;
  dfs(safe, safe); 
  for (int v = 0; v < n; ++v) {
    int mx = 0; 
    for (int u : g[v]) {
      if (dist[v] != dist[u] + 1) {
        mx = max(mx, sz[u]);   
      } else {
        mx = max(mx, n - sz[v]);
      }
    }
    for (int u : g[v]) {
      if (dist[v] == dist[u] + 1) {
        ties[v] = mx == (n - sz[v]);
      }
    }
  }
  return ties;
}
 
void locate(vector<pair<int, int>> F, int curr, int t) {
  int n = (int) F.size() + 1; 
  vector<vector<int>> g(n); 
  for (int i = 0; i < n - 1; ++i) {
    auto [u, v] = F[i];
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u); 
  }
  vector<int> sz(n); 
  function<void(int, int)> dfs = [&](int v, int p) {
    sz[v] = 1;
    for (int u : g[v]) {
      if (u == p) {
        continue;
      }
      dfs(u, v);
      sz[v] += sz[u]; 
    }
  };
  --curr; 
  dfs(curr, curr); 
  function<bool(int, int, int, bool)> dfs2 = [&](int v, int p, int tt, bool deterministic) {
    vector<pair<int, int>> vec; 
    for (int u : g[v]) {
      int s = (sz[u] < sz[v] ? sz[u] : n - sz[v]);
      vec.push_back({s, u});
    }
    sort(vec.begin(), vec.end());
    if (tt == 1) {
      int x = vec.back().first;
      reverse(vec.begin(), vec.end());
      while (vec.back().first < x) {
        vec.pop_back();
      }
    } else {
      int x = vec.back().first; 
      while (vec.back().first == x) {
        vec.pop_back();
      }
    }
    for (auto [s, u] : vec) {
      if (u == p) {
        continue; 
      }
      bool nd = ((int) vec.size() == 1);
      int nt = visit(u + 1); 
      g[v].erase(find(g[v].begin(), g[v].end(), u));
      bool f = dfs2(u, v, nt, nd);         
      if (f == false) {
        visit(v + 1); 
      } else {
        return true; 
      }
    }
    return !tt;
  };
  dfs2(curr, curr, t, 0);
  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 764 KB Correct

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 16720 KB Correct
2 Correct 238 ms 16216 KB Correct
3 Correct 112 ms 16276 KB Correct
4 Correct 100 ms 13520 KB Correct
5 Correct 226 ms 15148 KB Correct
6 Correct 81 ms 11868 KB Correct
7 Correct 86 ms 11940 KB Correct
8 Correct 190 ms 16436 KB Correct
9 Correct 219 ms 16280 KB Correct
10 Correct 151 ms 13680 KB Correct
11 Correct 98 ms 14248 KB Correct
12 Correct 283 ms 17660 KB Correct
13 Correct 83 ms 11772 KB Correct
14 Correct 82 ms 11932 KB Correct
15 Correct 212 ms 16200 KB Correct
16 Correct 218 ms 16436 KB Correct
17 Correct 141 ms 13740 KB Correct
18 Correct 99 ms 14948 KB Correct
19 Correct 142 ms 14660 KB Correct
20 Correct 80 ms 11852 KB Correct
21 Correct 90 ms 11864 KB Correct
22 Correct 190 ms 16048 KB Correct
23 Correct 222 ms 16292 KB Correct
24 Correct 91 ms 13648 KB Correct
25 Correct 89 ms 15624 KB Correct
26 Correct 94 ms 14164 KB Correct
27 Correct 86 ms 11876 KB Correct
28 Correct 82 ms 11788 KB Correct
29 Correct 218 ms 16348 KB Correct
30 Correct 221 ms 16016 KB Correct
31 Correct 95 ms 12700 KB Correct
32 Correct 251 ms 16344 KB Correct
33 Correct 222 ms 16064 KB Correct
34 Correct 81 ms 11868 KB Correct
35 Correct 88 ms 11852 KB Correct
36 Correct 186 ms 16328 KB Correct
37 Correct 221 ms 16364 KB Correct
38 Correct 239 ms 17196 KB Correct
39 Correct 146 ms 14680 KB Correct
40 Correct 212 ms 15336 KB Correct
41 Correct 78 ms 11880 KB Correct
42 Correct 81 ms 12116 KB Correct
43 Correct 230 ms 16252 KB Correct
44 Correct 236 ms 16068 KB Correct
45 Correct 89 ms 14376 KB Correct
46 Correct 79 ms 14688 KB Correct
47 Correct 111 ms 13908 KB Correct
48 Correct 79 ms 11868 KB Correct
49 Correct 80 ms 12064 KB Correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 7504 KB Correct
2 Incorrect 73 ms 7840 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 764 KB Correct
2 Correct 221 ms 16720 KB Correct
3 Correct 238 ms 16216 KB Correct
4 Correct 112 ms 16276 KB Correct
5 Correct 100 ms 13520 KB Correct
6 Correct 226 ms 15148 KB Correct
7 Correct 81 ms 11868 KB Correct
8 Correct 86 ms 11940 KB Correct
9 Correct 190 ms 16436 KB Correct
10 Correct 219 ms 16280 KB Correct
11 Correct 151 ms 13680 KB Correct
12 Correct 98 ms 14248 KB Correct
13 Correct 283 ms 17660 KB Correct
14 Correct 83 ms 11772 KB Correct
15 Correct 82 ms 11932 KB Correct
16 Correct 212 ms 16200 KB Correct
17 Correct 218 ms 16436 KB Correct
18 Correct 141 ms 13740 KB Correct
19 Correct 99 ms 14948 KB Correct
20 Correct 142 ms 14660 KB Correct
21 Correct 80 ms 11852 KB Correct
22 Correct 90 ms 11864 KB Correct
23 Correct 190 ms 16048 KB Correct
24 Correct 222 ms 16292 KB Correct
25 Correct 91 ms 13648 KB Correct
26 Correct 89 ms 15624 KB Correct
27 Correct 94 ms 14164 KB Correct
28 Correct 86 ms 11876 KB Correct
29 Correct 82 ms 11788 KB Correct
30 Correct 218 ms 16348 KB Correct
31 Correct 221 ms 16016 KB Correct
32 Correct 95 ms 12700 KB Correct
33 Correct 251 ms 16344 KB Correct
34 Correct 222 ms 16064 KB Correct
35 Correct 81 ms 11868 KB Correct
36 Correct 88 ms 11852 KB Correct
37 Correct 186 ms 16328 KB Correct
38 Correct 221 ms 16364 KB Correct
39 Correct 239 ms 17196 KB Correct
40 Correct 146 ms 14680 KB Correct
41 Correct 212 ms 15336 KB Correct
42 Correct 78 ms 11880 KB Correct
43 Correct 81 ms 12116 KB Correct
44 Correct 230 ms 16252 KB Correct
45 Correct 236 ms 16068 KB Correct
46 Correct 89 ms 14376 KB Correct
47 Correct 79 ms 14688 KB Correct
48 Correct 111 ms 13908 KB Correct
49 Correct 79 ms 11868 KB Correct
50 Correct 80 ms 12064 KB Correct
51 Correct 78 ms 7504 KB Correct
52 Incorrect 73 ms 7840 KB Not correct
53 Halted 0 ms 0 KB -