Submission #1209257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209257		vincentbucourt1	Praktični (COCI18_prakticni)	C++20	130 / 130	129 ms	22736 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 INF = (int)1e18;
const int MAXV = 100'020;

int V, E;
struct Edge {
    int u, v, w, i;
    int move (int x) {
        if (x == u) return v;
        else return u;
    }
};
vector<Edge> edges;
vector<int> adj[MAXV];
int depth[MAXV];
int rootPath[MAXV];
vector<pair<int,int>> vecs;//{val, iEdge}

void dfs (int node, int par) {
    for (int iEdge : adj[node]) {
        int child = edges[iEdge].move(node), weight = edges[iEdge].w, idx = edges[iEdge].i;
        if (child != par && depth[child] < depth[node]) {
            // cerr << node+1 << " " << child+1 << " " << (rootPath[child]^rootPath[node]^weight) << "\n";
            if (rootPath[child] ^ rootPath[node] ^ weight != 0) {
                vecs.push_back({rootPath[child] ^ rootPath[node] ^ weight, iEdge});
            }
        }
        else if (depth[child] == INF) {
            // cerr << node+1 << " " << child+1 << "\n";
            depth[child] = depth[node] + 1;
            rootPath[child] = rootPath[node] ^ weight;
            dfs(child, node);
        }
    }
}

int lsb (int val) {
    assert(val != 0);
    for (int bit = 0; bit < 32; bit++) {
        if (val&(1 << bit)) {
            return bit;
        }
    }
}
bool cmpBv (const int& a, const int& b) {
    return lsb(a) < lsb(b);
}

signed main() {
    fastIO();
    cin >> V >> E;
    for (int i = 0; i < E; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        edges.push_back(Edge{u, v, w, i});
        adj[u].push_back((int)edges.size()-1);
        adj[v].push_back((int)edges.size()-1);
    }
    fill(depth, depth+V, INF);
    depth[0] = 0;
    dfs(0, -1);
    vector<int> baseVecs;
    map<int, vector<int>> baseVecsIdx;
    sort(vecs.begin(), vecs.end());
    vecs.erase(unique(vecs.begin(), vecs.end()), vecs.end());
    for (pair<int,int>& val : vecs) {//{val, iEdge}
        for (int& bv : baseVecs) {
            if (val.f == 0) {
                break;
            }
            else if (lsb(val.f) < lsb(bv)) {
                baseVecs.push_back(val.f);
                if (baseVecsIdx.find(val.f) == baseVecsIdx.end()) baseVecsIdx[val.f] = {};
                baseVecsIdx[val.f].push_back(val.s);
                break;
            }
            else if (lsb(val.f) == lsb(bv)) {
                baseVecsIdx[bv].push_back(val.s);
                val.f ^= bv;
            }
        }
        if (val.f != 0 && (baseVecs.empty() || lsb(val.f) > lsb(baseVecs.back()))) {
            baseVecs.push_back(val.f);
            if (baseVecsIdx.find(val.f) == baseVecsIdx.end()) baseVecsIdx[val.f] = {};
            baseVecsIdx[val.f].push_back(val.s);
        }
        sort(baseVecs.begin(), baseVecs.end(), cmpBv);
    }
    cout << (int)baseVecs.size() << "\n";
    for (int i = 0; i < (int)baseVecs.size(); i++) {
        cout << baseVecs[i] << " " << (int)baseVecsIdx[baseVecs[i]].size() << " ";
        for (int val : baseVecsIdx[baseVecs[i]]) {
            cout << val+1 << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

Compilation message (stderr)

parkticni.cpp: In function 'long long int lsb(long long int)':
parkticni.cpp:50:1: warning: control reaches end of non-void function [-Wreturn-type]
   50 | }
      | ^

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