oj.uz

Submission #109965

# Submission time Handle Problem Language Result Execution time Memory
109965 2019-05-08T13:08:25 Z szawinis Praktični (COCI18_prakticni) C++17
130 / 130
 171 ms 16756 KB 
/**
 * 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 d[N], 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]) {
                if(d[e.v] < d[u]) {
//                    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 {
                d[e.v] = d[u] + 1;
                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);
                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

parkticni.cpp: In member function 'void TaskE::solve(std::istream&, std::ostream&)':
parkticni.cpp:59: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
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 7416 KB Output is correct
2 Correct 43 ms 7288 KB Output is correct
3 Correct 15 ms 4684 KB Output is correct
4 Correct 13 ms 4608 KB Output is correct
5 Correct 102 ms 10872 KB Output is correct
6 Correct 100 ms 9904 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5504 KB Output is correct
2 Correct 22 ms 5628 KB Output is correct
3 Correct 39 ms 6008 KB Output is correct
4 Correct 36 ms 6392 KB Output is correct
5 Correct 103 ms 10356 KB Output is correct
6 Correct 51 ms 8824 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8092 KB Output is correct
2 Correct 88 ms 9032 KB Output is correct
3 Correct 6 ms 3584 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 9708 KB Output is correct
2 Correct 117 ms 14464 KB Output is correct
3 Correct 7 ms 3712 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8696 KB Output is correct
2 Correct 103 ms 8668 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 11512 KB Output is correct
2 Correct 66 ms 7032 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 9808 KB Output is correct
2 Correct 119 ms 12760 KB Output is correct
3 Correct 113 ms 9012 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 13904 KB Output is correct
2 Correct 171 ms 16756 KB Output is correct
3 Correct 141 ms 15216 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5624 KB Output is correct
2 Correct 47 ms 6428 KB Output is correct
3 Correct 106 ms 10960 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 10688 KB Output is correct
2 Correct 63 ms 7772 KB Output is correct
3 Correct 125 ms 14256 KB Output is correct