제출 #1289047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289047		altern23	The Ties That Guide Us (CEOI23_incursion)	C++20	0 / 100	144 ms	7364 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) {
                  found &= visit(i);
                  return find_centroid_2(i, idx);
            }
      }

      if (!found) {
            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);

      solve(start, -1);
}

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