oj.uz

Submission #1040662

# Submission time Handle Problem Language Result Execution time Memory
1040662 2024-08-01T08:17:37 Z 우민규(#10996) The Ties That Guide Us (CEOI23_incursion) C++17
0 / 100
 191 ms 21148 KB 
#include <vector>
#include "incursion.h"
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;

std::vector<int> mark(std::vector<std::pair<int, int>> f, int safe) {
  int n = f.size() + 1;
  safe -= 1;
  vector<int> sz(n), maxsz(n);
  vector<vector<int>> adj(n);
  vector<int> par(n, -1), to_safe(n, -1);
  for (auto [u, v] : f) {
    adj[u - 1].push_back(v - 1);
    adj[v - 1].push_back(u - 1);
  }
  function<void(int, int)> dfs_sz = [&](int node, int par) {
    sz[node] = 1;
    maxsz[node] = 0;
    for (auto v : adj[node]) {
      if (v == par) continue;
      dfs_sz(v, node);
      maxsz[node] = max(maxsz[node], sz[v]);
      sz[node] += sz[v];
    }
    maxsz[node] = max(maxsz[node], n - sz[node]);
  };
  dfs_sz(0, -1);
  // check centroid count
  int cent_req = *min_element(maxsz.begin(), maxsz.end());
  vector<int> centroids;
  for (int i = 0; i < n; ++i) {
    if (maxsz[i] == cent_req) {
      centroids.push_back(i);
    }
  }
  assert(0 < centroids.size() && centroids.size() <= 2);

  
  function<void(int, vector<int>&)> dfs_par = [&](int node, vector<int>& par) {
    for (auto v : adj[node]) {
      if (v == par[node]) continue;
      par[v] = node;
      dfs_par(v, par);
    }
  };

  dfs_par(centroids[0], par);
  dfs_par(safe, to_safe);
  if (centroids.size() == 2) {
    par[centroids[0]] = centroids[1];
  }
  vector<int> ret;
  // true -> go to parent
  // false -> go to other child
  for (int i = 0; i < n; ++i) {
    if (to_safe[i] == par[i]) {
      ret.push_back(true);
    } else {
      ret.push_back(false);
    }
  }

  return ret;
}

void locate(std::vector<std::pair<int, int>> F, int node, int t) {
  node -= 1;
  int n = F.size() + 1;
  vector<vector<int>> adj(n);
  vector<int> sz(n), maxsz(n);
  vector<int> par(n, -1);
  vector<bool> visited(n, false);
  visited[node] = true;
  for (auto [u, v] : F) {
    adj[u - 1].push_back(v - 1);
    adj[v - 1].push_back(u - 1);
  }

  function<void(int, int)> dfs_sz = [&](int node, int par) {
    sz[node] = 1;
    maxsz[node] = 0;
    for (auto v : adj[node]) {
      if (v == par) continue;
      dfs_sz(v, node);
      maxsz[node] = max(maxsz[node], sz[v]);
      sz[node] += sz[v];
    }
    maxsz[node] = max(maxsz[node], n - sz[node]);
  };
  dfs_sz(0, -1);
  // check centroid count
  int cent_req = *min_element(maxsz.begin(), maxsz.end());
  vector<int> centroids;
  for (int i = 0; i < n; ++i) {
    if (maxsz[i] == cent_req) {
      centroids.push_back(i);
    }
  }
  assert(0 < centroids.size() && centroids.size() <= 2);

  function<void(int, vector<int>&)> dfs_par = [&](int node, vector<int>& par) {
    for (auto v : adj[node]) {
      if (v == par[node]) continue;
      par[v] = node;
      dfs_par(v, par);
    }
  };
  dfs_par(centroids[0], par);

  if (centroids.size() == 2) {
    par[centroids[0]] = centroids[1];
  }

  auto go = [&](int node) {
    visited[node] = true;
    return visit(node + 1);
  };


  while (true) {
    if (t) {
      if (visited[par[node]]) {
        go(par[node]);
        break;
      }
      t = go(par[node]);
      node = par[node];
      continue;
    }
    // node the singular centroid
    // try all ways
    bool moved = false;
    for (auto v : adj[node]) {
      if (v == par[node]) continue;
      if (visited[v]) continue;
      int ct = go(v);
      if (ct) {
        go(node);
      } else {
        t = ct;
        node = v;
        moved = true;
        break;
      }
    }
    if (!moved) break;
  }
  int x = 3;
}

#ifndef EVAL
#include "sample_grader.cpp"
#endif

Compilation message

incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:149:7: warning: unused variable 'x' [-Wunused-variable]
  149 |   int x = 3;
      |       ^
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
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 15448 KB Correct
2 Correct 191 ms 16240 KB Correct
3 Correct 95 ms 16444 KB Correct
4 Correct 104 ms 16160 KB Correct
5 Correct 181 ms 16360 KB Correct
6 Correct 74 ms 15880 KB Correct
7 Runtime error 72 ms 21148 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8800 KB Correct
2 Incorrect 76 ms 8632 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 190 ms 15448 KB Correct
3 Correct 191 ms 16240 KB Correct
4 Correct 95 ms 16444 KB Correct
5 Correct 104 ms 16160 KB Correct
6 Correct 181 ms 16360 KB Correct
7 Correct 74 ms 15880 KB Correct
8 Runtime error 72 ms 21148 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -