Submission #109963

#	Time	Username	Problem	Language	Result	Execution time	Memory
109963		szawinis	Praktični (COCI18_prakticni)	C++17	0 / 130	169 ms	15600 KiB

parkticni

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <bits/stdc++.h>
using namespace std;
#define long long long
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 1e5+1;

struct edge {
    int v, w, i;
    edge(int v, int w, int i): v(v), w(w), i(i) {}
};

class TaskE {

    int n, m;
    vector<edge> g[N];
    vector<pair<int,int> > vals;
    int basis[32];

    int f[N];
    bool mark[N];
    void dfs(int u, int par) {
        mark[u] = true;
        for(auto e: g[u]) {
            if(e.v == par) continue;
            if(mark[e.v]) {
//                cerr << u << ' ' << e.v << ' ' << (f[u] ^ f[e.v] ^ e.w) << endl;
                vals.emplace_back(f[u] ^ f[e.v] ^ e.w, e.i);
            } else {
                f[e.v] = f[u] ^ e.w;
                dfs(e.v, u);
            }
        }
    }

public:
    void solve(istream &cin, ostream &cout) {
        cin >> n >> m;
        for(int i = 0, u, v, w; i < m; i++) {
            cin >> u >> v >> w;
            g[u].emplace_back(v, w, i + 1);
            g[v].emplace_back(u, w, i + 1);
        }
        dfs(1, 0);
        vector<vector<int> > ans;
        for(int j = 31; j >= 0; j--) {
            vector<int> tmp;
            for(int i = 0; i < vals.size(); i++) if(vals[i].first >> j & 1) {
//                cerr << (1 << j) << ' ' << vals[i].first << ' ' << vals[i].second << endl;
                if(!basis[j]) {
                    basis[j] = vals[i].first;
                    tmp.push_back(vals[i].second);
                } else {
                    if(vals[i].first > (vals[i].first ^ basis[j])) {
                        tmp.push_back(vals[i].second);
                    }
                }
                vals[i].first ^= basis[j];
            }
            if(tmp.empty()) continue;
            tmp.insert(tmp.begin(), tmp.size());
            tmp.insert(tmp.begin(), basis[j]);
            ans.push_back(tmp);
        }
        cout << ans.size() << '\n';
        for(vector<int> v: ans) {
            for(int x: v) cout << x << ' ';
            cout << '\n';
        }
    }
};

class Solver {
public:
    void solve(std::istream& in, std::ostream& out) {
        TaskE *obj = new TaskE();
        obj->solve(in, out);
        delete obj;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    Solver solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}

Compilation message (stderr)

parkticni.cpp: In member function 'void TaskE::solve(std::istream&, std::ostream&)':
parkticni.cpp:56:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < vals.size(); i++) if(vals[i].first >> j & 1) {
                            ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 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