Submission #980920

#TimeUsernameProblemLanguageResultExecution timeMemory
980920RedGrey1993JOI tour (JOI24_joitour)C++17
32 / 100
486 ms204372 KiB
#include "joitour.h" #include <bits/stdc++.h> using namespace std; template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &pa) { is >> pa.first >> pa.second; return is; } template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; } template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; } template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; } template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template <typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } template <typename T> void resize_array(vector<T> &vec, int len) { vec.resize(len); } template <typename T, typename... Args> void resize_array(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) resize_array(v, args...); } template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); } template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); } long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; } mt19937 mrand(random_device{}()); int rnd(int x) { return mrand() % x; } #define rep(i, a, n) for (int i = a; i < (n); i++) #define per(i, a, n) for (int i = (n)-1; i >= a; i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define fi first #define se second #define sz(x) ((int)(x).size()) typedef vector<int> vi; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int, int> pii; typedef double db; #if DEBUG #define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl; #else #define dbg(x) #endif template <typename T> class StaticTopTree { public: enum Type { Vertex, Compress, Rake, AddEdge, AddVertex }; StaticTopTree(vector<vector<int>> &g, int root = 0) : g_(g), root_(root) { int n = g_.size(); parent_.resize(4 * n, -1); left_.resize(4 * n, -1); right_.resize(4 * n, -1); vertex_type_.resize(4 * n, Type::Vertex); paths_.resize(4 * n); points_.resize(4 * n); cur_idx_ = n; build(); } private: // do HLD(Heavy Light Decomposition), move heavy edge to g_[c][0]; int dfs(int c) { int s = 1, best = 0; for (int &d : g_[c]) { int t = dfs(d); s += t; if (best < t) best = t, swap(d, g_[c][0]); } return s; } int add(int k, int l, int r, Type t) { if (k == -1) k = cur_idx_++; parent_[k] = -1, left_[k] = l, right_[k] = r, vertex_type_[k] = t; if (l != -1) parent_[l] = k; if (r != -1) parent_[r] = k; return k; } pair<int, int> merge(const vector<pair<int, int>> &a, Type t) { if (a.size() == 1) return a[0]; int u = 0; for (auto &[_, s] : a) u += s; vector<pair<int, int>> b, c; // make sure b/c at least has 1 item for (auto& [i, s] : a) (u > s ? b : c).emplace_back(i, s), u -= s * 2; // if use (u > 0 ? b : c), c may be 0 size, will be RE // for (auto &[i, s] : a) (u > 0 ? b : c).emplace_back(i, s), u -= s * 2; auto [i, si] = merge(b, t); auto [j, sj] = merge(c, t); return {add(-1, i, j, t), si + sj}; } pair<int, int> compress(int i) { vector<pair<int, int>> chs{add_vertex(i)}; while (!g_[i].empty()) chs.push_back(add_vertex(i = g_[i][0])); return merge(chs, Type::Compress); } pair<int, int> rake(int i) { vector<pair<int, int>> chs; for (int j = 1; j < (int)g_[i].size(); j++) chs.push_back(add_edge(g_[i][j])); return chs.empty() ? make_pair(-1, 0) : merge(chs, Type::Rake); } pair<int, int> add_edge(int i) { auto [j, sj] = compress(i); return {add(-1, j, -1, Type::AddEdge), sj}; } pair<int, int> add_vertex(int i) { auto [j, sj] = rake(i); return {add(i, j, -1, j == -1 ? Type::Vertex : Type::AddVertex), sj + 1}; } void build() { dfs(root_); auto [i, n] = compress(root_); stt_root_ = i; } // private: public: // adjacent list of initial tree, chridren are stored in g_[parent], // parent can not be stored in g_[child] in this implement!!! // g_ must be a rooted tree vector<vector<int>> &g_; int root_; // an index of the root in g int stt_root_; // an index of the root in static top tree vector<int> parent_, left_, right_; // parent, left child, right child vector<Type> vertex_type_; // type of vertices int cur_idx_; // a variable for the index increment vector<int> values; private: // u: upper boundary vertex, v: lower boundary vertex struct TP { // ll fv; ll c012,c01u,c2,c0,cu12,c01v,cv12,cu1v,c0_u_2,cvu_2,c0_uv; friend ostream &operator<<(ostream &os, const TP &p) { return os << "c012:" << p.c012 << "\n" << "c01u:" << p.c01u << "\n" << "c2:" << p.c2 << "\n" << "c0:" << p.c0 << "\n" << "cu12:" << p.cu12 << "\n" << "c01v:" << p.c01v << "\n" << "cv12:" << p.cv12 << "\n" << "cu1v:" << p.cu1v << "\n" << "c0_u_2:" << p.c0_u_2 << "\n" << "cvu_2:" << p.cvu_2 << "\n" << "c0_uv:" << p.c0_uv << "\n"; } }; using Point = TP; using Path = TP; vector<Point> points_; vector<Path> paths_; Path vertex(int i) { TP tp; // tp.fv= values[i]; tp.c012 = 0; tp.c01u = 0; tp.c2 = (values[i] == 2); tp.c0 = (values[i] == 0); tp.cu12 = 0; tp.c01v = 0; tp.cv12 = 0; tp.cu1v = (values[i] == 1); tp.c0_u_2 = 0; tp.cvu_2 = 0; tp.c0_uv = 0; return tp; } Path compress(Path p, Path c) { TP tp; // tp.fv = c.fv; tp.c012 = p.c012 + c.c012 + p.c01v * c.c2 + p.cv12 * c.c0 + p.c0 * c.cu12 + p.c2 * c.c01u; tp.c01u = p.c01u + c.c01u + p.cu1v * c.c0; tp.c2 = p.c2 + c.c2; tp.c0 = p.c0 + c.c0; tp.cu12 = p.cu12 + c.cu12 + p.cu1v * c.c2; tp.c01v = p.c01v + c.c01v + p.c0 * c.cu1v; tp.cv12 = p.cv12 + c.cv12 + p.c2 * c.cu1v; tp.cu1v = p.cu1v + c.cu1v; // tp.c0_u_2 = p.c0_u_2 + c.c0 * p.cvu_2 + c.c2 * p.c0_uv; tp.c0_u_2 = 0; tp.cvu_2 = p.cvu_2; tp.c0_uv = p.c0_uv; return tp; } Path add_vertex(Point p, int i) { TP tp; // tp.fv = values[i]; tp.c012 = p.c012 + p.cu12 * (values[i] == 0) + p.c01u * (values[i] == 2) + p.c0_u_2 * (values[i] == 1); tp.c01u = p.c01u + p.c0 * (values[i] == 1); tp.c2 = p.c2 + (values[i] == 2); tp.c0 = p.c0 + (values[i] == 0); tp.cu12 = p.cu12 + (values[i] == 1) * p.c2; tp.c01v = p.c01u + (values[i] == 1) * p.c0; tp.cv12 = p.cu12 + (values[i] == 1) * p.c2; tp.cu1v = (values[i] == 1); tp.c0_u_2 = p.c0_u_2; tp.cvu_2 = p.c2; tp.c0_uv = p.c0; return tp; } Point add_edge(Path p) { return p; } Point rake(Point p, Point c) { TP tp; // tp.fv = values[i]; tp.c012 = p.c012 + c.c012; tp.c01u = p.c01u + c.c01u; tp.c2 = p.c2 + c.c2; tp.c0 = p.c0 + c.c0; tp.cu12 = p.cu12 + c.cu12; tp.c01v = p.c01u + c.c01u; tp.cv12 = p.cu12 + c.cu12; tp.cu1v = 0; tp.c0_u_2 = p.c0 * c.c2 + p.c2 * c.c0; // tp.cvu_2 = 0; // tp.c0_uv = 0; return tp; } void update_node(int k) { if (vertex_type_[k] == Vertex) paths_[k] = vertex(k); else if (vertex_type_[k] == Compress) paths_[k] = compress(paths_[left_[k]], paths_[right_[k]]); else if (vertex_type_[k] == AddVertex) paths_[k] = add_vertex(points_[left_[k]], k); else if (vertex_type_[k] == AddEdge) points_[k] = add_edge(paths_[left_[k]]); else if (vertex_type_[k] == Rake) points_[k] = rake(points_[left_[k]], points_[right_[k]]); } void init(int k) { if (left_[k] != -1) init(left_[k]); if (right_[k] != -1) init(right_[k]); update_node(k); dbg(mp(k, vertex_type_[k])); dbg(points_[k]); dbg(paths_[k]); } public: void update_tree(int k, T v) { values[k] = v; while (k != -1) { update_node(k); k = parent_[k]; } } void init() { init(stt_root_); } T get_answer() { return paths_[stt_root_].c012; } }; unique_ptr<StaticTopTree<ll>> p_stt = nullptr; void init(int N, std::vector<int> F, std::vector<int> U, std::vector<int> V, int Q) { vector<vi> edges(N); rep(i,0,N-1) { edges[U[i]].emplace_back(V[i]); edges[V[i]].emplace_back(U[i]); } vector<vi> g(N); function<void(int,int)> dfs=[&] (int u, int p) { for(int v : edges[u]) { if (v != p) { g[u].emplace_back(v); dfs(v, u); } } }; dfs(0, -1); dbg(g); p_stt = make_unique<StaticTopTree<ll>>(g); p_stt->values = F; dbg(p_stt->values); p_stt->init(); } void change(int X, int Y) { p_stt->update_tree(X, Y); } long long num_tours() { return p_stt->get_answer(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...