Submission #1284268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284268		AbdullahIshfaq	The Ties That Guide Us (CEOI23_incursion)	C++20	0 / 100	57 ms	7668 KiB

incursion

#include <bits/stdc++.h>
#include "incursion.h"
using namespace std;
#define ll long long
#define MOD 998244353

int n;
vector<int> sz, par, vis, res;
vector<vector<int>> g;

void dfs(int u, int v)
{
  par[u] = v;
  for (auto i : g[u]){
    if (i != v){
      dfs(i, u);
      sz[u] += sz[i];
    }
  }
  if(n - sz[u] >= (n + 1) / 2){
    res[u - 1] = 1;
  }
}

void dfs2(int u, int t)
{
  vis[u] = 1;
  if (t)
  {
    for (auto i : g[u]){
      if ((sz[i] >= (n + 1) / 2 and !vis[i])){
        dfs2(i, visit(i));
      }
    }
  }
  else
  {
    vector<pair<int, int>> tmp;
    for (auto i : g[u]){
      if (!vis[i] and i != par[u] and sz[i] < (n + 1) / 2){
        tmp.push_back({sz[i], i});
      }
    }
    sort(tmp.rbegin(), tmp.rend());
    if (!tmp.empty()){
      dfs2(tmp[0].second, visit(tmp[0].second));
    }
  }
}

vector<int> mark(vector<pair<int, int>> edg, int safe)
{
  n = edg.size() + 1;
  g.resize(n + 1);
  par.resize(n + 1);
  sz.resize(n + 1, 1);
  res.resize(n);
  for (auto i : edg){
    g[i.first].push_back(i.second);
    g[i.second].push_back(i.first);
  }
  dfs(safe, -1);
  return res;
}

void locate(vector<pair<int, int>> edg, int curr, int t)
{
  g.clear();
  sz.clear();
  par.clear();
  vis.clear();
  res.clear();
  n = edg.size() + 1;
  g.resize(n + 1);
  vis.resize(n + 1);
  par.resize(n + 1);
  sz.resize(n + 1, 1);
  res.resize(n);
  for (auto i : edg){
    g[i.first].push_back(i.second);
    g[i.second].push_back(i.first);
  }
  dfs(curr, -1);
  dfs2(curr, t);
}

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