oj.uz

Submission #230504

# Submission time Handle Problem Language Result Execution time Memory
230504 2020-05-10T08:59:59 Z VEGAnn Praktični (COCI18_prakticni) C++14
26 / 130
 130 ms 17912 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 = 20;
vector<pair<int, vector<int> > > result;
vector<int> extra, ids;
vector<pii> vc;
vector<pii> g[N];
int U[N], V[N], C[N], pre[N], pr[N][PW], xr[N], tt = 0, tin[N], tout[N];
int n, m;

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){
    tin[v] = tt++;

    pr[v][0] = p;

    for (int po = 1; po < PW; po++)
        pr[v][po] = pr[v][pr[v][po - 1]];

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

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

        dfs(u.ft, v);
    }

    tout[v] = tt++;
}

bool upper(int a, int b){
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}

int lca(int a, int b){
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;

    for (int po = PW - 1; po >= 0; po--)
        if (!upper(pr[a][po], b))
            a = pr[a][po];

    return pr[a][0];
}

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]--;

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

    if (sz(vc) == 0)
        cout << 0;
    else {
        for (int bt = 0; bt < 30; bt++){
            int ost = -1;

            ids.clear();

            for (pii cr : vc)
                if (cr.sd & (1 << bt)){
                    ids.PB(cr.ft);

                    if (ost < 0)
                        ost = cr.sd;
                    else ost &= cr.sd;
                }

            if (ost < 0) continue;

            result.PB(MP(ost, ids));

            for (pii &cr : vc)
                if (cr.sd & (1 << bt))
                    cr.sd ^= ost;
        }

        cout << sz(result) << '\n';

        for (pair<int, vector<int> > cr : result){
            cout << cr.ft << " " << sz(cr.sd);

            for (int vls : cr.sd)
                cout << " " << vls + 1;

            cout << '\n';
        }
    }

    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 7288 KB Output is correct
2 Correct 53 ms 8952 KB Output is correct
3 Correct 13 ms 3488 KB Output is correct
4 Correct 13 ms 4224 KB Output is correct
5 Correct 112 ms 17912 KB Output is correct
6 Correct 107 ms 17656 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4352 KB Output is correct
2 Correct 21 ms 4480 KB Output is correct
3 Correct 28 ms 6272 KB Output is correct
4 Correct 35 ms 7032 KB Output is correct
5 Correct 70 ms 11768 KB Output is correct
6 Correct 50 ms 8184 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 9592 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 14620 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 11896 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 12416 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 15864 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 17784 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 7288 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 16760 KB Too many operations
2 Halted 0 ms 0 KB -