oj.uz

답안 #96291

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
96291 2019-02-07T20:51:16 Z dalgerok Praktični (COCI18_prakticni) C++14
26 / 130
 101 ms 12564 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;
}

vector < int > bas;
map < int, vector < int > > ans;
inline void add(int x){
    for(auto it : bas){
        x = min(x, (x ^ it));
    }
    if(!x){
        return;
    }
    for(auto &it : bas){
        it = min(it, (it ^ x));
    }
    bas.push_back(x);
    sort(bas.rbegin(), bas.rend());
}
inline void upd(int x, int y){
    int cur = 0;
    for(auto it : bas){
        if((x ^ it) < x){
            cur ^= it;
            x ^= it;
        }
    }
    ans[cur].push_back(y);
}

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);
    for(auto it : e){
        if(it.first){
            add(it.first);
        }
    }
    for(auto it : e){
        if(it.first){
            upd(it.first, it.second);
        }
    }
    cout << (int)ans.size() << "\n";
    for(auto it : ans){
        cout << it.first << " " << (int)it.second.size() << " ";
        for(auto x : it.second){
            cout << x << " ";
        }
        cout << "\n";
    }
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 6216 KB Output is correct
2 Correct 31 ms 7288 KB Output is correct
3 Correct 11 ms 3832 KB Output is correct
4 Correct 10 ms 3704 KB Output is correct
5 Correct 70 ms 11964 KB Output is correct
6 Correct 63 ms 11056 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 4444 KB Output is correct
2 Correct 25 ms 4988 KB Output is correct
3 Correct 20 ms 5496 KB Output is correct
4 Correct 25 ms 6008 KB Output is correct
5 Correct 57 ms 11088 KB Output is correct
6 Correct 42 ms 7872 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 41 ms 7284 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 57 ms 8800 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 41 ms 7416 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 67 ms 8300 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 84 ms 9224 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 101 ms 12564 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 4732 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 82 ms 9976 KB Too many operations
2 Halted 0 ms 0 KB -