oj.uz

Submission #1073384

# Submission time Handle Problem Language Result Execution time Memory
1073384 2024-08-24T13:52:33 Z NeroZein The Ties That Guide Us (CEOI23_incursion) C++17
0 / 100
 296 ms 17128 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<void(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) {
        int u = vec.back().second;
        vec.pop_back();
        g[v].erase(find(g[v].begin(), g[v].end(), u));
      }
    } else {
      int x = vec[0].first; 
      while (vec.back().first == x) {
        int u = vec.back().second;
        g[v].erase(find(g[v].begin(), g[v].end(), u));
        vec.pop_back();
      }
    }
    for (auto [s, u] : vec) {
      bool nd = ((int) vec.size() == 1);
      if (nd == true || u != p) {
        int nt = visit(u + 1); 
        g[v].erase(find(g[v].begin(), g[v].end(), u));
        return dfs2(u, v, nt, nd);         
      }
    }
  };
  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 1 ms 772 KB Correct

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 15808 KB Correct
2 Correct 195 ms 16568 KB Correct
3 Correct 126 ms 16208 KB Correct
4 Correct 112 ms 13396 KB Correct
5 Correct 222 ms 14676 KB Correct
6 Correct 90 ms 11788 KB Correct
7 Correct 88 ms 12092 KB Correct
8 Correct 213 ms 15932 KB Correct
9 Correct 217 ms 16704 KB Correct
10 Correct 170 ms 13468 KB Correct
11 Correct 99 ms 15024 KB Correct
12 Correct 296 ms 17128 KB Correct
13 Correct 81 ms 11932 KB Correct
14 Correct 90 ms 11928 KB Correct
15 Correct 221 ms 15812 KB Correct
16 Correct 238 ms 15840 KB Correct
17 Correct 119 ms 13844 KB Correct
18 Incorrect 94 ms 14940 KB Not correct
19 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 7580 KB Correct
2 Incorrect 86 ms 7512 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 772 KB Correct
2 Correct 217 ms 15808 KB Correct
3 Correct 195 ms 16568 KB Correct
4 Correct 126 ms 16208 KB Correct
5 Correct 112 ms 13396 KB Correct
6 Correct 222 ms 14676 KB Correct
7 Correct 90 ms 11788 KB Correct
8 Correct 88 ms 12092 KB Correct
9 Correct 213 ms 15932 KB Correct
10 Correct 217 ms 16704 KB Correct
11 Correct 170 ms 13468 KB Correct
12 Correct 99 ms 15024 KB Correct
13 Correct 296 ms 17128 KB Correct
14 Correct 81 ms 11932 KB Correct
15 Correct 90 ms 11928 KB Correct
16 Correct 221 ms 15812 KB Correct
17 Correct 238 ms 15840 KB Correct
18 Correct 119 ms 13844 KB Correct
19 Incorrect 94 ms 14940 KB Not correct
20 Halted 0 ms 0 KB -