제출 #1150985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150985		polarity	Training (IOI07_training)	C++20	100 / 100	7 ms	4680 KiB

training

/**
 * Solution by 1egend (polarity.sh)
 * Date: 2025-02-11
 * Contest: IOI 2007
 * Problem: training
**/

#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
#define pb push_back
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAX_N = 1e5 + 1;
const ll MOD = 1e9 + 7;


/** TOOL: Debug
 *  PURPOSE: Prints various data types to terminal
 *  SOURCE: tourist
*/
template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

/**
 * DATASTRUCTURE: Sparse Table
 * PURPOSE: Efficient RMQ
 * TIME: O(n log n) preprocessing and O(1) queries
 */
template <typename T> class SparseTable {
  private:
	int n, log2dist;
    vector<vector<T>> st;

  public:
	SparseTable(const vector<T> &v) {
		n = (int)v.size();
		log2dist = 1 + (int)log2(n);
		st.resize(log2dist);
		st[0] = v;
		for (int i = 1; i < log2dist; i++) {
			st[i].resize(n - (1 << i) + 1);
			for (int j = 0; j + (1 << i) <= n; j++) {
				st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
			}
		}
	}

	/** @return minimum on the range [l, r] */
	T query(int l, int r) {
		int i = (int)log2(r - l + 1);
		return min(st[i][l], st[i][r - (1 << i) + 1]);
	}
};

/**
 * ALGORITHM: Lowest Common Ancestor
 * PURPOSE: Lowest common ancestor node of two nodes, also supports depth and distance of nodes
 * TIME: O(n) preprocessing, O(log N) lca query
 * REQUIRE: Segment Tree (or another RMQ structure)
 */
class LCA {
    private: 
        /** IN SEGTREE REMEMBER TO SET UNIT = pii{INT_MAX, INT_MAX} */
        SparseTable<pii> st;
        vi first;
        vi last;
        vi tour;
        vi d;

    public:
        LCA(int n, vector<vector<int>> &adj) : st({{0, 0}}), first(n), last(n), tour(2 * n - 1), d(n) {
            int i = -1;
            function<void(int, int, int)> dfs;
            dfs = [&](int node, int parent, int depth){
                tour[++i] = node;
                first[node] = i;
                d[node] = depth;
                for (int x : adj[node]){
                    if (x != parent){
                        dfs(x, node, depth + 1);
                        tour[++i] = node;
                    }
                }
                last[node] = i;
            };

            // root at 0
            dfs(0, 0, 0);

            vector<pii> arr = vector<pii>(2 * n - 1);

            rep(i, 0, 2 * n - 1){
                arr[i] = {d[tour[i]], tour[i]};
            }

            st = SparseTable<pii>(arr);
        }

        int idx(int node){
            return first[node];
        }

        int depth(int node){
            return d[node];
        }

        int inSubtree(int a, int b){
            return first[a] <= first[b] && first[b] <= last[a];
        }

        int lca(int a, int b){
            pii range = minmax(first[a], first[b]);
            /** IN SPARSE TABLE REMEMBER TO USE INCLUSIVE BOUND range.second */
            return st.query(range.first, range.second).second;
        }

        int dist(int a, int b){
            return d[a] + d[b] - 2 * d[lca(a, b)];
        }
};

vector<vi> adj;
vi par;
vi branches;
vi branch;
vi bipartition;

void dfs(int node, int parent, int depth){
    par[node] = parent;
    branch[node] = 1 << branches[parent];
    branches[parent]++;
    bipartition[node] = depth % 2;

    for (int x : adj[node]){
        if (x == parent){
            continue;
        }

        dfs(x, node, depth + 1);
    }
}

void solve(){
    int n, m; cin >> n >> m;

    vector<array<int, 4>> edges(m);
    
    vector<vi> dp(n, vi(1 << 10));
    adj = vector<vi>(n);
    par = vi(n);
    branches = vi(n, 0);
    branch = vi(n);
    bipartition = vi(n, 0);

    int total = 0;

    rep(i, 0, m){
        int a, b, c; cin >> a >> b >> c;
        --a; --b;
        if (c == 0){
            adj[a].pb(b);
            adj[b].pb(a);
        } else {
            total += c;
        }

        edges[i] = {0, c, a, b};
    }

    LCA lca = LCA(n, adj);

    rep(i, 0, m){
        edges[i][0] = lca.lca(edges[i][2], edges[i][3]);
    }

    auto cmp = [&](array<int, 4> &x, array<int, 4> &y) { 
        return lca.idx(x[0]) > lca.idx(y[0]);
    };

    sort(all(edges), cmp);

    dfs(0, 0, 0);

    rep(i, 0, m){
        auto [x, c, a, b] = edges[i];

        if (bipartition[a] != bipartition[b] && c != 0){
            continue;
        }

        // if choose a-b in subtree x
        int add = c;

        // remove path edges and add along the way
        int masked;
        int msk = 0;
        int curr = a;
        while(curr != x){
            add += dp[curr][msk];
            msk = branch[curr];
            curr = par[curr];
        }

        masked = msk;

        msk = 0, curr = b;
        while(curr != x){
            add += dp[curr][msk];
            msk = branch[curr];
            curr = par[curr];
        }

        masked |= msk;

        // go through all removals
        for (int mask = (1 << branches[x]) - 1; mask >= 0; mask--){
            if ((mask & masked) != 0){
                continue;
            }

            dp[x][mask] = max(dp[x][mask], add + dp[x][mask | masked]);
        }
    }

    cout << total - dp[0][0] << endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 7 / 7
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9