oj.uz

Submission #546931

# Submission time Handle Problem Language Result Execution time Memory
546931 2022-04-09T00:55:12 Z jeroenodb Praktični (COCI18_prakticni) C++17
130 / 130
 161 ms 18152 KB 
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
vi adj[mxN];

vi base;
int pref[mxN];
bitset<mxN> vis,mark;
vector<array<int,3>> es;
vector<pi> bad;
void dfs(int at, int from) {
    vis[at]=true;
    mark[at]=true;
    for(auto ei : adj[at]) {
        auto& e = es[ei];
        int to = e[0]^e[1]^at, w= e[2];
        if(to==from) continue;
        if(!vis[to]) {
            pref[to]=pref[at]^w;
            dfs(to,at);
        } else if(mark[to])  {
            // back edge
            int cyc = pref[at]^pref[to]^w;
            bad.push_back({ei,cyc});
            for(auto i : base) cyc = min(cyc,i^cyc);
            if(cyc!=0) base.push_back(cyc);
        }
    }
    mark[at]=false;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m; cin >> n >> m;
    es.resize(m);
    for(int i=0;i<m;++i) {
        auto& [a,b,w] = es[i];
        cin >> a >> b >> w;
        adj[a].push_back(i);
        adj[b].push_back(i);

    }
    dfs(1,0);
    vvi res(base.size());
    sort(all(bad));
    for(auto [i,cyc] : bad) {
        for(int j=0;j<(int)base.size();++j) {
            if((cyc^base[j]) < cyc) {
                cyc ^=base[j];
                res[j].push_back(i+1);
            }
        }
    }
    cout << base.size() << '\n';
    auto it = base.begin();
    for(auto& i : res) {
        cout << *(it++) << ' ';
        cout << i.size() << ' ';
        cout << i << '\n';
    }
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7800 KB Output is correct
2 Correct 32 ms 8132 KB Output is correct
3 Correct 7 ms 3844 KB Output is correct
4 Correct 7 ms 4052 KB Output is correct
5 Correct 56 ms 14708 KB Output is correct
6 Correct 56 ms 13004 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4864 KB Output is correct
2 Correct 14 ms 5124 KB Output is correct
3 Correct 18 ms 6044 KB Output is correct
4 Correct 23 ms 6432 KB Output is correct
5 Correct 48 ms 12160 KB Output is correct
6 Correct 30 ms 8496 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8600 KB Output is correct
2 Correct 60 ms 10464 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 11588 KB Output is correct
2 Correct 105 ms 16568 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9792 KB Output is correct
2 Correct 52 ms 10056 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 12292 KB Output is correct
2 Correct 47 ms 7544 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 11928 KB Output is correct
2 Correct 82 ms 14468 KB Output is correct
3 Correct 56 ms 10544 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 16272 KB Output is correct
2 Correct 161 ms 18152 KB Output is correct
3 Correct 116 ms 17996 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5544 KB Output is correct
2 Correct 27 ms 6716 KB Output is correct
3 Correct 88 ms 12940 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 13196 KB Output is correct
2 Correct 48 ms 8744 KB Output is correct
3 Correct 140 ms 17140 KB Output is correct