Submission #1289062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289062		altern23	The Ties That Guide Us (CEOI23_incursion)	C++20	0 / 100	185 ms	7328 KiB

incursion

#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int MAXN = 5e4;

vector <ll> adj[MAXN + 5];
ll up[MAXN + 5], sz[MAXN + 5], N;

ll find_centroid(ll idx, ll par) {
      for (auto i : adj[idx]) {
            if (i != par && sz[i] > N / 2) {
                  return find_centroid(i, idx);
            }
      }
      return idx;
}

void dfs(ll idx, ll par) {
      sz[idx] = 1;
      for (auto i : adj[idx]) {
            if (i != par) {
                  up[i] = idx;
                  dfs(i, idx);
                  sz[idx] += sz[i];
            }
      }
}

vector <int> mark(vector <pair<int, int>> F, int safe) {
      N = -1;

      for (auto [i, j] : F) {
            adj[i].push_back(j), adj[j].push_back(i);

            N = max({N, (ll)i, (ll)j});
      }
      
      // check kalo safe itu centroid bukan

      dfs(safe, -1);

      bool centroid = 1;
      for(auto i : adj[safe]) {
            if(sz[i] > N / 2) centroid = 0;
      }

      dfs(1, -1);
      
      ll start;

      if(centroid) {
            start = safe;
      }
      else start = find_centroid(1, -1);

      dfs(start, -1);
      
      ll cur = safe;

      vector <int> A(N);

      while (cur != start) {
            A[cur - 1] = 1;
            cur = up[cur];
      }

      A[start - 1] = 1;
      
      for (int i = 1; i <= N; i++) {
            adj[i].clear();
            up[i] = sz[i] = 0;
      }

      return A;
}

ll find_centroid_2(ll idx, ll par) {
      bool found = 1;
      for (auto i : adj[idx]) {
            if (i != par && sz[i] > N / 2) {
                  if(visit(i)) return i;
                  return find_centroid_2(i, idx);
            }
      }

      for (auto i : adj[idx]) {
            if (i != par && sz[i] == N / 2) {
                  visit(i);
                  return i;
            }
      }

      return idx;
}

void solve(ll idx, ll par) {
      vector <ll> candidates;
      for (auto i : adj[idx]) {
            if (i != par) {
                  candidates.push_back(i);
            }
      }

      sort(candidates.begin(), candidates.end(), [&](ll a, ll b){
            return sz[a] > sz[b];
      });

      for (auto i : candidates) {
            if (visit(i)) {
                  solve(i, idx);
                  break;
            }
            visit(idx);
      }
}

void locate(vector <pair<int, int>> F, int curr, int t) {
      N = -1;

      for (auto [i, j] : F) {
            adj[i].push_back(j), adj[j].push_back(i);

            N = max({N, (ll)i, (ll)j});
      }
      
      dfs(curr, -1);

      ll start = find_centroid_2(curr, -1);

      dfs(start, -1);
      
      solve(start, -1);
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40