Submission #1209229

#TimeUsernameProblemLanguageResultExecution timeMemory
1209229vincentbucourt1Praktični (COCI18_prakticni)C++20
0 / 130
39 ms14500 KiB
#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; } } return 32; } 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; 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] << " "; for (int val : baseVecsIdx[baseVecs[i]]) { cout << val+1 << " "; } cout << "\n"; } cout << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...