제출 #96291

#제출 시각아이디문제언어결과실행 시간메모리
96291dalgerokPraktični (COCI18_prakticni)C++14
26 / 130
101 ms12564 KiB
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int n, m, d[N], cl[N]; vector < pair < pair < int, int >, int > > g[N]; vector < pair < int, int > > e; void dfs(int v, int pr = -1){ cl[v] = 1; for(auto it : g[v]){ int to = it.first.first, len = it.first.second; if(to != pr){ if(!cl[to]){ d[to] = (d[v] ^ len); dfs(to, v); } else if(cl[to] == 1){ e.push_back(make_pair((d[v] ^ len ^ d[to]), it.second)); } } } cl[v] = 2; } vector < int > bas; map < int, vector < int > > ans; inline void add(int x){ for(auto it : bas){ x = min(x, (x ^ it)); } if(!x){ return; } for(auto &it : bas){ it = min(it, (it ^ x)); } bas.push_back(x); sort(bas.rbegin(), bas.rend()); } inline void upd(int x, int y){ int cur = 0; for(auto it : bas){ if((x ^ it) < x){ cur ^= it; x ^= it; } } ans[cur].push_back(y); } int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> m; for(int i = 1; i <= m; i++){ int x, y, z; cin >> x >> y >> z; g[x].push_back(make_pair(make_pair(y, z), i)); g[y].push_back(make_pair(make_pair(x, z), i)); } dfs(1); for(auto it : e){ if(it.first){ add(it.first); } } for(auto it : e){ if(it.first){ upd(it.first, it.second); } } cout << (int)ans.size() << "\n"; for(auto it : ans){ cout << it.first << " " << (int)it.second.size() << " "; for(auto x : it.second){ cout << x << " "; } 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...