Submission #1183214

#TimeUsernameProblemLanguageResultExecution timeMemory
1183214PlayVoltzThe Ties That Guide Us (CEOI23_incursion)C++20
100 / 100
146 ms8008 KiB
#include <bits/stdc++.h> #include "incursion.h" using namespace std; #define pii pair<int, int> #define mp make_pair #define pb push_back #define fi first #define se second int n; vector<int> sz, res, pp; vector<bool> visited; vector<vector<int> > graph; void dfs(int node, int par){ pp[node]=par; for (auto num:graph[node])if (num!=par)dfs(num, node), sz[node]+=sz[num]; res[node-1]=(n-sz[node]>=(n+1)/2); } void dfs2(int node, int t){ visited[node]=1; if (t){for (auto num:graph[node])if ((sz[num]>=(n+1)/2&&!visited[num])||(num==pp[node]&&n-sz[node]>=(n+1)/2))dfs2(num, visit(num));} else{ vector<pii> temp; for (auto num:graph[node])if (!visited[num]&&num!=pp[node]&&sz[num]<(n+1)/2)temp.pb(mp(sz[num], num)); sort(temp.begin(), temp.end(), greater<pii>()); if (temp.size())dfs2(temp[0].se, visit(temp[0].se)); } } vector<int> mark(vector<pii> vect, int safe){ graph.clear(); sz.clear(); res.clear(); pp.clear(); n=vect.size()+1; graph.resize(n+1); res.resize(n); pp.resize(n+1); sz.resize(n+1, 1); for (auto a:vect)graph[a.fi].pb(a.se), graph[a.se].pb(a.fi); dfs(safe, -1); return res; } void locate(vector<pii> vect, int node, int b){ graph.clear(); sz.clear(); res.clear(); pp.clear(); visited.clear(); n=vect.size()+1; graph.resize(n+1); res.resize(n); visited.resize(n+1, 0); pp.resize(n+1); sz.resize(n+1, 1); for (auto a:vect)graph[a.fi].pb(a.se), graph[a.se].pb(a.fi); dfs(node, -1); dfs2(node, b); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...