Submission #1073398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073398		NeroZein	The Ties That Guide Us (CEOI23_incursion)	C++17	0 / 100	215 ms	16436 KiB

incursion

#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) {
        vec.pop_back();
      }
    } else {
      int x = vec[0].first; 
      while (vec.back().first > x) {
        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 (stderr)

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
• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40