Submission #96292

#	Time	Username	Problem	Language	Result	Execution time	Memory
96292		dalgerok	Praktični (COCI18_prakticni)	C++14	130 / 130	184 ms	17396 KiB

parkticni

#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;
}

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);
    vector < vector < int > > ans;
    for(int i = 0; i < 30; i++){
        int val = -1;
        for(auto it : e){
            if((it.first >> i) & 1){
                val = it.first;
            }
        }
        if(val == -1){
            continue;
        }
        vector < int > q;
        for(auto &it : e){
            if((it.first >> i) & 1){
                it.first ^= val;
                q.push_back(it.second);
            }
        }
        q.insert(q.begin(), (int)q.size());
        q.insert(q.begin(), val);
        ans.push_back(q);
    }
    cout << (int)ans.size() << "\n";
    for(auto it : ans){
        for(auto x : it){
            cout << x << " ";
        }
        cout << "\n";
    }
}

• 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