Praktični
레이팅 미적용의견: 0
1 \(s / 64\) \(MB / 130\) points
While writing an exam, Ivan had problems with the following task:
"In the input there is an integer number N. Find the N {th}{ } digit of the number 0.135791113151719 ..."
In order to succeed in the next attempt to pass the exam and so saving himself from repeating the
academic year, he decided to practice by being the main character in tasks such as the following:
An undirected graph of \(N\) nodes and \(M\) edges is given. Each edge has a value, an integer number
less than 10 {9}{ }.
A simple cycle (a cycle without repeating nodes) is good if the bitwise XOR of all the values of the
cycle’s edges is equal to zero.
Ivan can make a number of operations on the graph. An operation consists of the following steps:
●
Ivan selects an integer number \(x\) ;
●
then he selects a n\(on-em\)pty subset of edges of the given graph;
●
and then he applies bitwise XOR by number \(x\) on all the the selected edges (If one of the
selected edges has a value \(p\) , after the described operation, the new value of that edge will be
equal to \(p\) XOR \(x\) )
Ivan wants to obtain a graph in which every simple cycle is good. Also, he wants to do so in as few
operations as possible. Determine the minimum possible number of operations after which each
simple cycle is good and print them. It can be proved that it is always possible to meet Ivan's
requirements with a certain sequence of operations.
In the test samples worth 20% of the total points, the minimum number of required operations will be
equal to 1.
In the test samples worth additional 40% of the total points all the numbers from input will be less
than or equal to 10 {6}{ }.
1 \(s / 64\) \(MB / 130\) points
The first line contains two positive integers \(N\) and \(M\) (1 ≤ N, \(M\) ≤100 000), the number of nodes and
the number of edges.
In the i {th}{ } of the following \(M\) lines there is a description of the \(i\) {th}{ } edge: three integer numbers \(a\) {i}{ }, \(b\) {i}{ }i \(p\) {i}
(1 ≤ \(a\) { }, \(b\) { }≤ N, a { } ≠ \(b\) { }, { }0 ≤ \(p\) {i}{ }≤ 10 {9}{ }), the nodes connected with the \(i\) {th}{ } edge and the value of the edge.
The graph is connected and all the edges are different.
In the first line of output, print \(K\) , minimum number of task operations.
In each of the following \(K\) lines, print a sequence numbers separated by space:
●
the first number in the row is the number \(x\) from the operation;
●
the second number is \(B\) , the number of selected bridges;
●
then follows \(B\) numbers, \(E\) {i} (1 ≤ \(E\) ≤ \(M\) ) which indicate labels of the selected edges in the
ascending order.
All numbers in the output should be less than or equal to \(2 \cdot 10\) {9}{ }.
4 4
1 2 10
2 3 9
3 4 8
4 1 7
2 1
1 2 3
6 8
1 2 6
2 3 1
3 5 6
3 1 5
4 5 0
3 6 0
4 2 8
4 1 1output
output
1
12 3 1 2 3
0
2
2 2 4 6
15 1 7Explanation of test samples:
In the first test sample, the initial graph is given in the image left below, and the final graph (after applying XOR
on the first three edges with 12) is given in the image right below. The only cycle in the graph is good because
XOR of its edges is 0.
In the second test sample, there is no cycle, so the claim "every simple cycle is good" is trivially fulfilled. That is
why the number of required operations is 0.
평가 및 의견
Praktični
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Praktični