Submission #899321

#TimeUsernameProblemLanguageResultExecution timeMemory
899321RedGrey1993Training (IOI07_training)C++17
100 / 100
31 ms12896 KiB
#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; } template <unsigned int MOD> class ModInt { public: // static unsigned int MOD; ModInt(unsigned long long _v = 0) { set_v((_v % MOD + MOD)); } explicit operator bool() const { return val != 0; } ModInt operator-() const { return ModInt() - *this; } ModInt operator+(const ModInt &r) const { return ModInt().set_v(val + r.val); } ModInt operator-(const ModInt &r) const { return ModInt().set_v(val + MOD - r.val); } ModInt operator*(const ModInt &r) const { return ModInt().set_v((unsigned int)((unsigned long long)(val)*r.val % MOD)); } ModInt operator/(const ModInt &r) const { return *this * r.inv(); } ModInt &operator+=(const ModInt &r) { return *this = *this + r; } ModInt &operator-=(const ModInt &r) { return *this = *this - r; } ModInt &operator*=(const ModInt &r) { return *this = *this * r; } ModInt &operator/=(const ModInt &r) { return *this = *this / r; } // ModInt &operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return *this; } unsigned int operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return val; } bool operator==(const ModInt &r) const { return val == r.val; } bool operator!=(const ModInt &r) const { return val != r.val; } ModInt pow(long long n) const { ModInt x = *this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; } ModInt inv() const { return pow(MOD - 2); } unsigned int get_val() { return val; } friend ostream &operator<<(ostream &os, const ModInt &r) { return os << r.val; } friend istream &operator>>(istream &is, ModInt &r) { return is >> r.val; } private: unsigned int val; ModInt &set_v(unsigned int _v) { val = (_v < MOD) ? _v : _v - MOD; return *this; } }; constexpr unsigned int mod = 1e9+7; using Mint = ModInt<mod>; #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 using Mint2 = ModInt<mod-1>; class Solution { struct Edge { int u,v; int cost; friend ostream &operator<<(ostream &os, const Edge &r) { return os << r.u << "-->" << r.v << ":" << r.cost; } }; struct LCA { int node; int son1=-1, son2=-1; friend ostream &operator<<(ostream &os, const LCA &r) { return os << r.node << "(" << r.son1 << ", " << r.son2 << ")"; } }; public: void Solve() { int n,m; // n<=1000, m<=5000 while(cin>>n>>m) { int total_cost = 0; vi degree(n); vector<vi> tree_edges(n); vector<Edge> edges; int u,v,c; rep(i,0,m) { cin>>u>>v>>c; u--; v--; degree[u]++; degree[v]++; if (c == 0) { tree_edges[u].emplace_back(v); tree_edges[v].emplace_back(u); } else { edges.emplace_back(Edge{u,v,c}); total_cost += c; } } int max_degree = 1; rep(i,0,n) max_degree = *max_element(all(degree)); int bit_num = 1; while ((1<<bit_num) < n) bit_num++; vector<vi> parent(n, vi(bit_num)); // nth_son[i] indicates the orinary number of which son of the father [i] is. // nth_son[i] 表示i是父节点的第几个子节点 vi nth_son(n); function<void(int,int)> dfs2 = [&] (int u, int p) { rep(i,0,sz(tree_edges[u])) { int v = tree_edges[u][i]; if (v != p) { parent[v][0] = u; nth_son[v] = i; dfs2(v, u); } } }; parent[0][0] = -1; nth_son[0] = -1; dfs2(0, -1); // O(nlogn) rep(d,1,bit_num) { rep(u, 0, n) { if (parent[u][d-1] == -1) parent[u][d] = -1; else parent[u][d] = parent[parent[u][d-1]][d-1]; } } // O(n*m) vector<vi> tree_path_len(n, vi(n)); int root = 0; function<void(int,int,int)> dfs1 = [&] (int u, int p, int d) { tree_path_len[root][u] = d; for (int v : tree_edges[u]) { if (v != p) dfs1(v, u, d+1); } }; for (root = 0; root < n; root++) { dfs1(root, -1, 0); } // dbg(tree_path_len); vector<Edge> even_edges; for (auto edge : edges) { if (tree_path_len[edge.u][edge.v] % 2 == 0) { even_edges.emplace_back(edge); } } auto get_depth = [&] (int idx) { int depth = 0; int d = sz(parent[0]) - 1; while(idx != 0) { // dbg(mp(idx, d)); if (parent[idx][d] != -1) { depth |= (1<<d); idx = parent[idx][d]; } d--; } return depth; }; // least common ancestor auto get_lca = [&] (int u, int v) { int d1 = get_depth(u); int d2 = get_depth(v); // dbg(mp(d1,d2)); if (d1 < d2) { swap(u, v); } LCA lca; int t = abs(d1 - d2); if (t>0) { t--; rep(i,0,sz(parent[0])) { if (t & (1<<i)) u = parent[u][i]; } lca.son1 = nth_son[u]; u = parent[u][0]; } if (u == v) { lca.node = u; return lca; } int d = sz(parent[0]) - 1; // dbg(d); // dbg(mp(u,v)) while(d >= 0) { // dbg(mp(parent[u][d], parent[v][d])); if (parent[u][d] != parent[v][d]) { u = parent[u][d]; v = parent[v][d]; } // dbg(d); // dbg(mp(u,v)); d--; } lca.son1 = nth_son[u]; lca.son2 = nth_son[v]; lca.node = parent[u][0]; return lca; }; // O(mlogn) vector<vi> node_to_even_edges(n); vector<vector<pii>> node_to_direct_sons(n); rep(i,0,sz(even_edges)) { // dbg(mp(even_edges[i].u, even_edges[i].v)); LCA lca = get_lca(even_edges[i].u, even_edges[i].v); // dbg(lca); node_to_even_edges[lca.node].emplace_back(i); node_to_direct_sons[lca.node].emplace_back(mp(lca.son1, lca.son2)); } // O(m*2^k) vector<vi> dp(n, vi(1<<max_degree, -1)); vector<vi> cache(n, vi(n, -1)); rep(i,0,n) cache[i][i] = 0; rep(u,0,n) { for(int v : tree_edges[u]) { cache[u][v] = cache[v][u] = 0; } } function<int(int,int)> get_most_cost = [&] (int node, int mask) { // dbg(mp(node, mask)); if (dp[node][mask] != -1) return dp[node][mask]; int cost = 0; rep(i,0,sz(tree_edges[node])) { if ((1<<i) & mask) continue; if (tree_edges[node][i] == parent[node][0]) continue; cost += get_most_cost(tree_edges[node][i], 0); } dp[node][mask] = max(dp[node][mask], cost); if (node == 0 && mask == 0) { dbg("+++++++++"); dbg(cost); } rep(idx,0,sz(node_to_even_edges[node])) { int i = node_to_even_edges[node][idx]; if (node_to_direct_sons[node][idx].first != -1 && (mask & (1<<node_to_direct_sons[node][idx].first))) continue; if (node_to_direct_sons[node][idx].second != -1 && (mask & (1<<node_to_direct_sons[node][idx].second))) continue; cost = even_edges[i].cost; if (node == 0 && mask == 0) { dbg("---------"); dbg(cost); } int u = even_edges[i].u, v= even_edges[i].v; if (u != node) cost += get_most_cost(u, 0); if (node == 0 && mask == 0) dbg(cost); if (v != node) cost += get_most_cost(v, 0); if (node == 0 && mask == 0) dbg(cost); vi nodes, subtree_cost; while (true) { if (cache[node][u] != -1) { if (sz(nodes) > 0) { cache[node][nodes.back()] = subtree_cost.back() + cache[node][u]; per(i,0,sz(nodes)-1) { cache[node][nodes[i]] = subtree_cost[i] + cache[node][nodes[i+1]]; } } break; } int p = parent[u][0]; nodes.emplace_back(u); subtree_cost.emplace_back(get_most_cost(p, (1<<nth_son[u]))); u = p; } cost += cache[node][even_edges[i].u]; if (node == 0 && mask == 0) { dbg(subtree_cost); dbg(cost); } nodes.clear(), subtree_cost.clear(); while (true) { if (cache[node][v] != -1) { if (sz(nodes) > 0) { cache[node][nodes.back()] = subtree_cost.back() + cache[node][v]; per(i,0,sz(nodes)-1) { cache[node][nodes[i]] = subtree_cost[i] + cache[node][nodes[i+1]]; } } break; } int p = parent[v][0]; nodes.emplace_back(v); subtree_cost.emplace_back(get_most_cost(p, (1<<nth_son[v]))); v = p; } cost += cache[node][even_edges[i].v]; if (node == 0 && mask == 0) { dbg(subtree_cost); dbg(cost); } int mask2 = mask; if (node_to_direct_sons[node][idx].first != -1) mask2 |= (1<<node_to_direct_sons[node][idx].first); if (node_to_direct_sons[node][idx].second != -1) mask2 |= (1<<node_to_direct_sons[node][idx].second); if (node == 0 && mask == 0) dbg(mask2); cost += get_most_cost(node, mask2); if (node == 0 && mask == 0) dbg(cost); dp[node][mask] = max(dp[node][mask], cost); } // dbg(mp(node, mask)); // dbg(dp[node][mask]); return dp[node][mask]; }; cout << total_cost - get_most_cost(0, 0) << endl; } } private: }; // #define USACO 1 void set_io(const string &name = "") { ios::sync_with_stdio(false); cin.tie(nullptr); #if FILE_IO || USACO if (!name.empty()) { freopen((name + ".in").c_str(), "r", stdin); freopen((name + ".out").c_str(), "w", stdout); } #endif } int main() { #if USACO set_io("time"); #else set_io("input"); #endif Solution().Solve(); return 0; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...