oj.uz

Submission #1073389

# Submission time Handle Problem Language Result Execution time Memory
1073389 2024-08-24T13:56:53 Z NeroZein The Ties That Guide Us (CEOI23_incursion) C++17
0 / 100
 293 ms 17432 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) {
        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); 
        //if (deterministic && nd) {
          //exit(0); 
        //}
        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 0 ms 768 KB Correct

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 16576 KB Correct
2 Correct 209 ms 16632 KB Correct
3 Correct 111 ms 15776 KB Correct
4 Correct 119 ms 13188 KB Correct
5 Correct 198 ms 15288 KB Correct
6 Correct 83 ms 11876 KB Correct
7 Correct 86 ms 11880 KB Correct
8 Correct 218 ms 16028 KB Correct
9 Correct 223 ms 16192 KB Correct
10 Correct 164 ms 13616 KB Correct
11 Correct 108 ms 13984 KB Correct
12 Correct 293 ms 17432 KB Correct
13 Correct 88 ms 11792 KB Correct
14 Correct 84 ms 11852 KB Correct
15 Correct 213 ms 15964 KB Correct
16 Correct 211 ms 16276 KB Correct
17 Correct 115 ms 14036 KB Correct
18 Incorrect 90 ms 14748 KB Not correct
19 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 7776 KB Correct
2 Incorrect 77 ms 7844 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 768 KB Correct
2 Correct 237 ms 16576 KB Correct
3 Correct 209 ms 16632 KB Correct
4 Correct 111 ms 15776 KB Correct
5 Correct 119 ms 13188 KB Correct
6 Correct 198 ms 15288 KB Correct
7 Correct 83 ms 11876 KB Correct
8 Correct 86 ms 11880 KB Correct
9 Correct 218 ms 16028 KB Correct
10 Correct 223 ms 16192 KB Correct
11 Correct 164 ms 13616 KB Correct
12 Correct 108 ms 13984 KB Correct
13 Correct 293 ms 17432 KB Correct
14 Correct 88 ms 11792 KB Correct
15 Correct 84 ms 11852 KB Correct
16 Correct 213 ms 15964 KB Correct
17 Correct 211 ms 16276 KB Correct
18 Correct 115 ms 14036 KB Correct
19 Incorrect 90 ms 14748 KB Not correct
20 Halted 0 ms 0 KB -