oj.uz

Submission #256865

# Submission time Handle Problem Language Result Execution time Memory
256865 2020-08-03T10:22:38 Z Vladikus004 Praktični (COCI18_prakticni) C++14
26 / 130
 148 ms 12920 KB 
#include <bits/stdc++.h>
#define inf 2e9
//#define ff first
//#define ss second
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;

struct obj{
    int ff, ss, ind;
    obj(){
        ff = ss = ind = 0;
    }
    obj(int a, int b, int c){
        ff = a, ss = b, ind = c;
    }
};

const int N = 100000 + 3;
int n, m, p[N], w[N], nm[N], r[32][32], pr[32], ch[32], us[32];
vector <vector <obj> > v;
vector <obj> ed;
bitset <N> bs[32];

void dfs(int x, int pr){
    p[x] = 1;
    for (auto u: v[x]){
        if (u.ff == pr) continue;
        if (p[u.ff]) {
            ed.push_back(obj(x, u.ff, u.ind));
            continue;
        }
        w[u.ff] = w[x] ^ u.ss;
        dfs(u.ff, x);
    }
}

void add(int x, int ind){
    for (int i = 0; i < 32; i++)
        if (x&(1LL<<i))
            bs[i][ind] = 1;
}

int get_anc(int x){
    if (pr[x] == x) return x;
    return pr[x] = get_anc(pr[x]);
}

void unite(int x, int y){
    x = get_anc(x), y = get_anc(y);
    if (x == y) return;
    pr[x] = y;
    ch[y] |= ch[x];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    cin >> n >> m;
    v.resize(n);
    for (int i = 0; i < m; i++){
        int x, y, c;
        cin >> x >> y >> c;
        --x; --y;
        v[x].push_back(obj(y, c, i));
        v[y].push_back(obj(x, c, i));
        nm[i] = c;
    }
//    return 0;
    dfs(0,-228);
    int i = 0;
    for (auto u: ed){
        int x = u.ff, y = u.ss, ind = u.ind;
        int xr = w[x] ^ w[y];
        add(w[x]^w[y]^nm[ind], ind);
        ++i;
    }

    for (int i = 0; i < 32; i++){
        pr[i] = i; ch[i] = (1LL<<i);
    }
    for (int i = 0; i < 32; i++){
        if (!bs[i].any()) continue;
        for (int j = 0; j < 32; j++){
            if (i == j) continue;
            if (!bs[j].any()) continue;
            if (bs[i] == bs[j])
                unite(i, j);
        }
    }
//    cout << bs[0] << "\n";
//    cout << bs[1] << "\n";
//    cout << bs[2] << "\n";
//    cout << bs[3] << "\n";
    vector <int> ans;
    for (int i = 0; i < 32; i++){
        if (!bs[i].any()) continue;
        int cur = get_anc(i);
        if (us[cur]) continue;
        us[cur] = 1;
        ans.push_back(cur);
    }
    cout << ans.size() << "\n";
    for (auto u: ans){
        cout << ch[u] << " " << bs[u].count() << " ";
//        cout << bs[u] << "!\n";
        for (int i = 0; i < m; i++)
            if (bs[u][i]) cout << i + 1 << " ";
        cout << "\n";
    }
}
/**
5 6
1 2 1
2 3 2
1 4 1
4 5 2
1 3 0
1 5 0
*/

Compilation message

parkticni.cpp: In function 'int main()':
parkticni.cpp:80:13: warning: unused variable 'xr' [-Wunused-variable]
         int xr = w[x] ^ w[y];
             ^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5500 KB Output is correct
2 Correct 35 ms 6836 KB Output is correct
3 Correct 8 ms 1984 KB Output is correct
4 Correct 7 ms 1792 KB Output is correct
5 Correct 74 ms 12920 KB Output is correct
6 Correct 72 ms 11896 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2812 KB Output is correct
2 Correct 15 ms 3392 KB Output is correct
3 Correct 19 ms 4224 KB Output is correct
4 Correct 24 ms 4920 KB Output is correct
5 Correct 67 ms 11632 KB Output is correct
6 Correct 38 ms 7420 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 13.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 13.0

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

Subtask #8
0 / 13.0

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

Subtask #9
0 / 13.0

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

Subtask #10
0 / 13.0

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