oj.uz

Submission #154205

# Submission time Handle Problem Language Result Execution time Memory
154205 2019-09-19T00:53:05 Z AQT Praktični (COCI18_prakticni) C++14
130 / 130
 296 ms 16756 KB 
#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<int> graph[100005];
pair<pair<int, int>, int> edge[100005];
bool vis[100005];
int dep[100005];
int c[40];
vector<int> v;
vector<int> ans[40];

void dfs(int n, int p){
    vis[n] = 1;
    for(auto e : graph[n]){
        int k = edge[e].first.first;
        if(k == n){
            k = edge[e].first.second;
        }
        if(!vis[k]){
            dep[k] = dep[n] ^ edge[e].second;
            dfs(k, n);
        }
        else if(p != k){
            v.push_back(e);
        }
    }
}

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i<=M; i++){
        cin >> edge[i].first.first >> edge[i].first.second >> edge[i].second;
        graph[edge[i].first.first].push_back(i);
        graph[edge[i].first.second].push_back(i);
    }
    dfs(1, 0);
    int out = 0;
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int e : v){
        int k = dep[edge[e].first.first]^dep[edge[e].first.second]^edge[e].second;
        for(int b = 29; b>=0; b--){
            if((k>>b)&1){
                if(c[b] == 0){
                    c[b] = k;
                    out++;
                }
                k ^= c[b];
                ans[b].push_back(e);
            }
        }
    }
    cout << out << "\n";
    for(int b = 29; b>=0; b--){
        if(c[b]){
            cout << c[b] << " ";
            cout << ans[b].size() << " ";
            for(int e : ans[b]){
                cout << e << " ";
            }
            cout << "\n";
        }
    }
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 6904 KB Output is correct
2 Correct 42 ms 7160 KB Output is correct
3 Correct 13 ms 3832 KB Output is correct
4 Correct 12 ms 3832 KB Output is correct
5 Correct 111 ms 12024 KB Output is correct
6 Correct 89 ms 11184 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4600 KB Output is correct
2 Correct 21 ms 4728 KB Output is correct
3 Correct 26 ms 5368 KB Output is correct
4 Correct 31 ms 5844 KB Output is correct
5 Correct 86 ms 10396 KB Output is correct
6 Correct 50 ms 7416 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7928 KB Output is correct
2 Correct 69 ms 9336 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 10232 KB Output is correct
2 Correct 129 ms 14656 KB Output is correct
3 Correct 6 ms 2808 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 8684 KB Output is correct
2 Correct 84 ms 9468 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 11244 KB Output is correct
2 Correct 45 ms 7032 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 10784 KB Output is correct
2 Correct 99 ms 13300 KB Output is correct
3 Correct 73 ms 9592 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 14580 KB Output is correct
2 Correct 151 ms 16756 KB Output is correct
3 Correct 296 ms 16108 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5368 KB Output is correct
2 Correct 35 ms 6264 KB Output is correct
3 Correct 90 ms 11512 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 11896 KB Output is correct
2 Correct 54 ms 7928 KB Output is correct
3 Correct 125 ms 15084 KB Output is correct