Submission #1204446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204446		vincentbucourt1	Praktični (COCI18_prakticni)	C++20	26 / 130	65 ms	22852 KiB

parkticni

#include <bits/stdc++.h>
using namespace std;
void fastIO(){ios_base::sync_with_stdio(false),cin.tie(0);}
#define int long long
#define f first
#define s second

const int MAXV = 100'020;
const int LOG = 30;

int V, E;
struct Edge {
    int to, cost, idx;
};
vector<Edge> adj[MAXV];
int depth[MAXV];
int rootPath[MAXV];
bool isChange[MAXV];
int valChange[MAXV];
vector<pair<int,vector<int>>> ans;

void dfs (int node, int par) {
    for (Edge nxt : adj[node]) {
        int child = nxt.to, cost = nxt.cost, idx = nxt.idx;
        if (child == par) {
            continue;
        }
        else if (depth[child] == -1) {
            depth[child] = depth[node] + 1;
            rootPath[child] = rootPath[node] ^ cost;
            dfs(child, node);
        }
        else if (depth[child] < depth[node]) {
            isChange[idx] = true;
            int underCost = rootPath[node] ^ rootPath[child];
            int xorVal = cost ^ underCost;
            valChange[idx] = xorVal;
        }
    }
}

signed main() {
    fastIO();
    cin >> V >> E;
    for (int i = 0; i < E; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        u--, v--;
        adj[u].push_back({v, c, i});
        adj[v].push_back({u, c, i});
    }
    fill(depth, depth+V, -1);
    depth[0] = 0;
    dfs(0, -1);
    vector<pair<vector<int>,int>> process(LOG);
    for (int i = 0; i < LOG; i++) {
        process[i].s = i;
    }
    for (int idx = 0; idx < E; idx++) {
        if (isChange[idx]) {
            for (int log = 0; log < LOG; log++) {
                if (valChange[idx] & (1 << log)) {
                    process[log].f.push_back(idx);
                }
            }
        }
    }
    sort(process.begin(), process.end());
    // for (int log = 0; log < LOG; log++) {
    //     cerr << process[log].s << ": ";
    //     for (int idx : process[log].f) {
    //         cerr << idx << " ";
    //     }
    //     cerr << "\n";
    // }
    vector<int> idxProcess;
    int valXor = 0;
    for (int log = 0; log < LOG; log++) {
        if (log != 0 && process[log].f != process[log-1].f) {
            if (!idxProcess.empty()) {
                ans.push_back(make_pair(valXor, idxProcess));
            }
            idxProcess.clear();
            valXor = 0;
        }
        for (int idx : process[log].f) {
            idxProcess.push_back(idx);
        }
        valXor ^= (1 << process[log].s);
    }
    if (!idxProcess.empty()) {
        ans.push_back(make_pair(valXor, idxProcess));
        idxProcess.clear();
    }
    cout << (int)ans.size() << "\n";
    for (pair<int,vector<int>> on : ans) {
        sort(on.s.begin(), on.s.end());
        on.s.erase(unique(on.s.begin(), on.s.end()), on.s.end());
        cout << on.f << " " << (int)on.s.size() << " ";
        for (int idx : on.s) {
            cout << idx+1 << " ";
        }
        cout << "\n";
    }
}

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