Submission #1224046

#TimeUsernameProblemLanguageResultExecution timeMemory
1224046spetrThe Ties That Guide Us (CEOI23_incursion)C++20
40 / 100
201 ms16088 KiB
#include <vector> #include "incursion.h" #include <cstdio> #include <bits/stdc++.h> using namespace std; #define vl vector <long long> #define ll long long #define vll vector<vector<long long>> vll graf; vector<int> ans; set<ll> vis; vl counts; void dfs(ll x, ll d){ ans[x-1] = d%3; vis.insert(x); for (ll i = 0; i < graf[x].size(); i++){ ll v = graf[x][i]; auto exist = vis.find(v); if (exist == vis.end()){ dfs(v, d+1); } } return; } std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) { vis.clear(); graf.clear(); ans.clear(); long long N = F.size()+1; ans.resize(N,0); for (ll i = 0; i < N+1; i++){graf.push_back({});} for (ll i = 0; i < F.size(); i++){ pair p = F[i]; graf[p.first].push_back(p.second); graf[p.second].push_back(p.first); } dfs(safe, 0); return ans; } void step(ll x, ll dist){ if (dist == 0){ dist = 3; } vl vektor = graf[x]; vector<pair<ll,ll>> opt; for (ll i = 0; i < vektor.size(); i++){ opt.push_back({counts[vektor[i]], vektor[i]}); } sort(opt.begin(), opt.end()); reverse(opt.begin(), opt.end()); for (ll i = 0; i < opt.size(); i++){ ll v = opt[i].second; auto exist = vis.find(v); if (exist == vis.end()){ ll p = visit(v); vis.insert(v); if (p + 1 == dist){ step(v, p); break; } else {p = visit(x);} } } return; } set<ll> y; ll find_count(ll x){ y.insert(x); ll suma = 1; for (ll i = 0; i < graf[x].size(); i++){ auto exist = y.find(graf[x][i]); if (exist == y.end()){ suma += find_count(graf[x][i]); } } counts[x] = suma; return suma; } void locate(std::vector<std::pair<int, int>> F, int curr, int t) { vis.clear(); graf.clear(); long long N = F.size()+1; counts.resize(N+1); for (ll i = 0; i < N+1; i++){graf.push_back({});} for (ll i = 0; i < F.size(); i++){ pair p = F[i]; graf[p.first].push_back(p.second); graf[p.second].push_back(p.first); } find_count(curr); vis.insert(curr); step(curr, t); return; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...