oj.uz

Submission #307317

# Submission time Handle Problem Language Result Execution time Memory
307317 2020-09-27T16:15:10 Z phathnv Praktični (COCI18_prakticni) C++11
130 / 130
 140 ms 14840 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "PRAKTICNI"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1e5 + 1;
const int logC = 30;

struct DSU{
    int root[N], rnk[N];
    void init(int n){
        for(int i = 1; i <= n; i++){
            root[i] = i;
            rnk[i] = 0;
        }
    }
    int getRoot(int u){
        if (u == root[u])
            return u;
        root[u] = getRoot(root[u]);
        return root[u];
    }
    bool unite(int u, int v){
        u = getRoot(u);
        v = getRoot(v);
        if (u == v)
            return 0;
        if (rnk[u] < rnk[v])
            swap(u, v);
        root[v] = u;
        rnk[u] += (rnk[u] == rnk[v]);
        return 1;
    }
};

struct edge{
    int u, v, c;
    edge(int _u = 0, int _v = 0, int _c = 0){
        u = _u;
        v = _v;
        c = _c;
    }
};

int n, m;
edge e[N];

bool mark[N];
vector <ii> adj[N];
int dist[N];

int bit[logC];
vector <int> res[logC];

void readInput(){
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++)
        scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].c);
}

void dfs(int u, int p){
    for(ii e : adj[u]){
        int v = e.X, c = e.Y;
        if (v == p)
            continue;
        dist[v] = dist[u] ^ c;
        dfs(v, u);
    }
}

void buildForest(){
    DSU dsu;
    dsu.init(n);
    for(int i = 1; i <= m; i++){
        int u = e[i].u, v = e[i].v, c = e[i].c;
        if (dsu.unite(u, v)){
            adj[u].push_back(mp(v, c));
            adj[v].push_back(mp(u, c));
            mark[i] = 1;
        }
    }
    for(int i = 1; i <= n; i++)
        if (i == dsu.getRoot(i))
            dfs(i, -1);
}

int getDist(int u, int v){
    return dist[u] ^ dist[v];
}

void solve(){
    vector <int> ind;
    for(int i = 1; i <= m; i++)
        if (!mark[i]){
            e[i].c ^= getDist(e[i].u, e[i].v);
            ind.push_back(i);
        }

    int cnt = 0;
    for(int i = 0; i < logC; i++)
        bit[i] = -1;
    for(int id : ind){
        int val = e[id].c;
        for(int i = 0; i < logC; i++){
            if (!((val >> i) & 1))
                continue;
            if (bit[i] == -1){
                bit[i] = val;
                cnt++;
            }
            val ^= bit[i];
            res[i].push_back(id);
        }
    }

    printf("%d\n", cnt);
    for(int i = 0; i < logC; i++){
        if (bit[i] == -1)
            continue;
        printf("%d %d ", bit[i], (int) res[i].size());
        for(int id : res[i])
            printf("%d ", id);
        printf("\n");
    }
}

int main(){
    //freopen(taskname".inp", "r", stdin);
    //freopen(taskname".out", "w", stdout);
    readInput();
    buildForest();
    solve();
    return 0;
}

Compilation message

parkticni.cpp: In function 'void readInput()':
parkticni.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
parkticni.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |         scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5496 KB Output is correct
2 Correct 37 ms 7032 KB Output is correct
3 Correct 9 ms 4352 KB Output is correct
4 Correct 11 ms 4608 KB Output is correct
5 Correct 89 ms 11896 KB Output is correct
6 Correct 92 ms 11384 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4480 KB Output is correct
2 Correct 16 ms 4992 KB Output is correct
3 Correct 23 ms 5760 KB Output is correct
4 Correct 27 ms 6016 KB Output is correct
5 Correct 66 ms 8824 KB Output is correct
6 Correct 39 ms 6904 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6904 KB Output is correct
2 Correct 65 ms 9212 KB Output is correct
3 Correct 4 ms 3840 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 7928 KB Output is correct
2 Correct 108 ms 12920 KB Output is correct
3 Correct 4 ms 3968 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 7064 KB Output is correct
2 Correct 78 ms 9720 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 8564 KB Output is correct
2 Correct 54 ms 7672 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 8824 KB Output is correct
2 Correct 103 ms 12536 KB Output is correct
3 Correct 67 ms 9464 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 11152 KB Output is correct
2 Correct 140 ms 14840 KB Output is correct
3 Correct 125 ms 14584 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5504 KB Output is correct
2 Correct 35 ms 6776 KB Output is correct
3 Correct 91 ms 11156 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 9464 KB Output is correct
2 Correct 53 ms 8440 KB Output is correct
3 Correct 116 ms 13676 KB Output is correct