oj.uz

Submission #230550

# Submission time Handle Problem Language Result Execution time Memory
230550 2020-05-10T11:09:19 Z VEGAnn Praktični (COCI18_prakticni) C++14
130 / 130
 128 ms 14964 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pii pair<int,int>
#define pis pair<int,short>
#define ft first
#define sd second
#define MP make_pair
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
const int oo = 2e9;
const int N = 100100;
const int PW = 30;
vector<int> extra, vec[PW];
vector<pii> g[N], vc;
int U[N], V[N], C[N], pre[N], xr[N], tt = 0;
int XOR = -1, n, m, basis[PW], siz = 0, id[PW], obr[PW];

bool cmp(int _x, int _y){
    return C[_x] < C[_y];
}

int get(int x) { return (pre[x] == x ? x : pre[x] = get(pre[x])); }

void dfs(int v, int p){
    for (pii u : g[v]){
        if (u.ft == p) continue;

        xr[u.ft] = (xr[v] ^ u.sd);

        dfs(u.ft, v);
    }
}

void insert_to_basis(int x){
    for (int po = 0; po < PW; po++){
        if (!(x & (1 << po)))
            continue;

        if (basis[po] == 0) {
            basis[po] = x;
            id[po] = siz;
            obr[siz] = po;
            siz++;
            return;
        } else x ^= basis[po];
    }
}

void add(pii x){
    for (int po = 0; po < PW; po++){
        if (!(x.sd & (1 << po)))
            continue;

        assert(basis[po] != 0);

        vec[id[po]].PB(x.ft);
        x.sd ^= basis[po];
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m;

    for (int i = 0; i < n; i++)
        pre[i] = i;

    for (int i = 0; i < m; i++){
        cin >> U[i] >> V[i] >> C[i];
        U[i]--; V[i]--;
    }

    for (int i = m - 1; i >= 0; i--){
        int x = get(U[i]), y = get(V[i]);

        if (x == y) {
            extra.PB(i);
        } else {
            pre[x] = y;
            g[U[i]].PB(MP(V[i], C[i]));
            g[V[i]].PB(MP(U[i], C[i]));
        }
    }

    dfs(0, 0);

    for (int nm : extra){
        int x = U[nm], y = V[nm];

        int cxr = (xr[x] ^ xr[y] ^ C[nm]);

        if (cxr != 0){
            vc.PB(MP(nm, cxr));
            insert_to_basis(cxr);
        }
    }

    if (!sz(vc))
        cout << 0;
    else {
        cout << siz << '\n';

        for (pii cr : vc)
            add(cr);

        for (int i = 0; i < siz; i++){
            cout << basis[obr[i]] << " " << sz(vec[i]);

            for (int cr : vec[i])
                cout << " " << cr + 1;

            cout << '\n';
        }
    }

    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4736 KB Output is correct
2 Correct 37 ms 5624 KB Output is correct
3 Correct 11 ms 3328 KB Output is correct
4 Correct 12 ms 3456 KB Output is correct
5 Correct 70 ms 10104 KB Output is correct
6 Correct 81 ms 9976 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3584 KB Output is correct
2 Correct 17 ms 4096 KB Output is correct
3 Correct 23 ms 4608 KB Output is correct
4 Correct 27 ms 4864 KB Output is correct
5 Correct 60 ms 7160 KB Output is correct
6 Correct 38 ms 5624 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 6136 KB Output is correct
2 Correct 58 ms 8696 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 7672 KB Output is correct
2 Correct 100 ms 12912 KB Output is correct
3 Correct 7 ms 2816 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 6528 KB Output is correct
2 Correct 72 ms 9208 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 8444 KB Output is correct
2 Correct 41 ms 6904 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 8312 KB Output is correct
2 Correct 94 ms 11904 KB Output is correct
3 Correct 60 ms 8952 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 11004 KB Output is correct
2 Correct 128 ms 14964 KB Output is correct
3 Correct 122 ms 14448 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4608 KB Output is correct
2 Correct 35 ms 6008 KB Output is correct
3 Correct 80 ms 10616 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 8952 KB Output is correct
2 Correct 49 ms 7672 KB Output is correct
3 Correct 112 ms 13504 KB Output is correct