제출 #1275457

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275457		Tai_xiu	Šarenlist (COCI22_sarenlist)	C++20	110 / 110	62 ms	660 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007LL;

ll modpow(ll a, ll e) {
    ll r = 1 % MOD;
    a %= MOD;
    while (e > 0) {
        if (e & 1) r = (r * a) % MOD;
        a = (a * a) % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const string NAME = "coloring";
    // If running with file io:
    // freopen((NAME + ".inp").c_str(), "r", stdin);
    // freopen((NAME + ".out").c_str(), "w", stdout);

    int n, m, k;
    if (!(cin >> n >> m >> k)) return 0;

    // adjacency: pair (neighbor, edgeIndex)
    vector<vector<pair<int,int>>> adj(n+1);
    for (int i = 1; i <= n-1; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    // parent, height and edgeToParent arrays (size n+1)
    vector<int> parent(n+1, 0), height(n+1, 0), edgeToParent(n+1, 0);
    // do DFS / stack to set parent, height, edgeToParent
    {
        stack<int> st;
        st.push(1);
        parent[1] = 0;
        height[1] = 0;
        while (!st.empty()) {
            int u = st.top(); st.pop();
            for (auto [v, ei] : adj[u]) {
                if (v == parent[u]) continue;
                parent[v] = u;
                edgeToParent[v] = ei; // edge index between v and parent[v]
                height[v] = height[u] + 1;
                st.push(v);
            }
        }
    }

    // read m queries, for each build vector of edge indices along path
    vector<vector<int>> path(m);
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        vector<int> edges_up, edges_down;

        // raise deeper node
        while (height[u] > height[v]) {
            edges_up.push_back(edgeToParent[u]);
            u = parent[u];
        }
        while (height[v] > height[u]) {
            edges_down.push_back(edgeToParent[v]);
            v = parent[v];
        }
        // now same height
        while (u != v) {
            edges_up.push_back(edgeToParent[u]);
            edges_down.push_back(edgeToParent[v]);
            u = parent[u];
            v = parent[v];
        }
        // path edges = edges_up followed by reverse(edges_down)
        path[i] = edges_up;
        for (int j = (int)edges_down.size() - 1; j >= 0; --j) path[i].push_back(edges_down[j]);
    }

    // quick check: if any path has < 1 edge then impossible? The original checked <2 because they stored edges differently.
    // For safety: if path empty (u==v) then this query contributes no edges; depending on problem statement that might be invalid.
    for (int i = 0; i < m; ++i) {
        if ((int)path[i].size() < 1) {
            cout << 0 << '\n';
            return 0;
        }
    }

    // initial answer: k^(n-1)  (color edges independently)
    ll sol = modpow(k, n - 1);

    // safety note: exponential in m. If m > 22 this loop is heavy. Assume problem constraints allow 2^m brute-force.
    if (m >= 60) {
        // extremely unlikely per problem constraints; but avoid UB with (1LL<<m)
        cerr << "Warning: m is large, brute-force over 2^m is infeasible/unsafe\n";
    }

    int totalMasks = 1 << m; // assume m <= 30-ish per constraints
    for (int mask = 1; mask < totalMasks; ++mask) {
        // build graph among edges (1..n-1) using selected paths
        vector<vector<int>> g1(n); // index by edge index (1..n-1). size n is enough
        vector<char> seen(n, 0); // seen[edgeIndex]
        for (int i = 0; i < m; ++i) if (mask & (1<<i)) {
            auto &vec = path[i];
            for (int j = 0; j + 1 < (int)vec.size(); ++j) {
                int a = vec[j], b = vec[j+1];
                g1[a].push_back(b);
                g1[b].push_back(a);
            }
        }
        // count connected components among edges 1..n-1 that are considered as graph nodes
        int cnt = 0;
        for (int e = 1; e <= n-1; ++e) {
            if (!seen[e]) {
                // but if no adjacency and also not present in any selected path, it is a singleton component
                ++cnt;
                // DFS
                stack<int> st; st.push(e); seen[e] = 1;
                while (!st.empty()) {
                    int x = st.top(); st.pop();
                    for (int y : g1[x]) if (!seen[y]) {
                        seen[y] = 1;
                        st.push(y);
                    }
                }
            }
        }
        int bits = __builtin_popcount((unsigned)mask);
        if (bits % 2 == 0) sol = (sol + modpow(k, cnt)) % MOD;
        else sol = (sol - modpow(k, cnt) + MOD) % MOD;
    }

    cout << sol << '\n';
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 65 / 65