oj.uz

Submission #96292

# Submission time Handle Problem Language Result Execution time Memory
96292 2019-02-07T20:55:02 Z dalgerok Praktični (COCI18_prakticni) C++14
130 / 130
 184 ms 17396 KB 
#include<bits/stdc++.h>
using namespace std;



const int N = 1e5 + 5;




int n, m, d[N], cl[N];
vector < pair < pair < int, int >, int > > g[N];
vector < pair < int, int > > e;

void dfs(int v, int pr = -1){
    cl[v] = 1;
    for(auto it : g[v]){
        int to = it.first.first, len = it.first.second;
        if(to != pr){
            if(!cl[to]){
                d[to] = (d[v] ^ len);
                dfs(to, v);
            }
            else if(cl[to] == 1){
                e.push_back(make_pair((d[v] ^ len ^ d[to]), it.second));
            }
        }
    }
    cl[v] = 2;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y, z;
        cin >> x >> y >> z;
        g[x].push_back(make_pair(make_pair(y, z), i));
        g[y].push_back(make_pair(make_pair(x, z), i));
    }
    dfs(1);
    vector < vector < int > > ans;
    for(int i = 0; i < 30; i++){
        int val = -1;
        for(auto it : e){
            if((it.first >> i) & 1){
                val = it.first;
            }
        }
        if(val == -1){
            continue;
        }
        vector < int > q;
        for(auto &it : e){
            if((it.first >> i) & 1){
                it.first ^= val;
                q.push_back(it.second);
            }
        }
        q.insert(q.begin(), (int)q.size());
        q.insert(q.begin(), val);
        ans.push_back(q);
    }
    cout << (int)ans.size() << "\n";
    for(auto it : ans){
        for(auto x : it){
            cout << x << " ";
        }
        cout << "\n";
    }
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6264 KB Output is correct
2 Correct 29 ms 6264 KB Output is correct
3 Correct 11 ms 3576 KB Output is correct
4 Correct 9 ms 3576 KB Output is correct
5 Correct 72 ms 9976 KB Output is correct
6 Correct 73 ms 9052 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4344 KB Output is correct
2 Correct 16 ms 4472 KB Output is correct
3 Correct 20 ms 4856 KB Output is correct
4 Correct 24 ms 5368 KB Output is correct
5 Correct 66 ms 9224 KB Output is correct
6 Correct 36 ms 6776 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 7032 KB Output is correct
2 Correct 63 ms 9508 KB Output is correct
3 Correct 3 ms 2680 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 8904 KB Output is correct
2 Correct 100 ms 15076 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 7672 KB Output is correct
2 Correct 57 ms 9592 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 10344 KB Output is correct
2 Correct 40 ms 7288 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 9208 KB Output is correct
2 Correct 83 ms 13008 KB Output is correct
3 Correct 51 ms 9720 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 12660 KB Output is correct
2 Correct 122 ms 17396 KB Output is correct
3 Correct 107 ms 16104 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 4600 KB Output is correct
2 Correct 28 ms 6264 KB Output is correct
3 Correct 73 ms 11640 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 9948 KB Output is correct
2 Correct 50 ms 8056 KB Output is correct
3 Correct 113 ms 15216 KB Output is correct