Submission #1204398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204398		vincentbucourt1	Praktični (COCI18_prakticni)	C++20	26 / 130	62 ms	16968 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;

int V, E;
struct Edge {
    int to, cost, idx;
};
vector<Edge> adj[MAXV];
int depth[MAXV];
int rootPath[MAXV];
map<int, vector<int>> toChange;

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 (rootPath[child] == -1) {
            rootPath[child] = rootPath[node] ^ cost;
            dfs(child, node);
        }
        else {
            int underCost = rootPath[node] ^ rootPath[child];
            int xorVal = cost ^ underCost;
            if (xorVal != 0 && toChange.find(xorVal) == toChange.end()) {
                toChange[xorVal] = {idx};
            }
            else if (xorVal != 0) {
                toChange[xorVal].push_back(idx);
            }
        }
    }
}

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(rootPath, rootPath+V, -1);
    rootPath[0] = 0;
    dfs(0, -1);
    cout << (int)toChange.size() << "\n";
    for (auto lIt = toChange.begin(); lIt != toChange.end(); lIt++) {
        pair<int,vector<int>> on = *lIt;
        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 val : on.s) {
            cout << val+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