oj.uz

Submission #463460

# Submission time Handle Problem Language Result Execution time Memory
463460 2021-08-11T07:50:26 Z grt Praktični (COCI18_prakticni) C++17
130 / 130
 138 ms 18016 KB 
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 100 * 1000 + 10, mod = 1e9 + 7, p = 31;
int n, m;
vector<pi>V[nax];
int cost[nax];
bool vis[nax];
int xr[nax];
vector<pi>num;
bool done[nax];

void dfs(int x, int par) {
	vis[x] = true;
	for(auto nbh : V[x]) if(nbh.ST != par) {
		if(!vis[nbh.ST]) {
			xr[nbh.ST] = xr[x] ^ cost[nbh.ND];
			dfs(nbh.ST, x);
		} else {
			if(done[nbh.ND]) continue;
			done[nbh.ND] = true;
			num.emplace_back(xr[x] ^ xr[nbh.ST] ^ cost[nbh.ND], nbh.ND);
		}
	}
}

int main() {_
	cin >> n >> m;
	for(int a, b, c, i = 1; i <= m; ++i) {
		cin >> a >> b >> c;
		V[a].emplace_back(b, i);
		V[b].emplace_back(a, i);
		cost[i] = c;
	}
	dfs(1, 0);
	int id = 0;
	vi res = {};
	vector<vi>ans = {};
	for(int bit = 30; bit >= 0; --bit) {
		bool any = false;
		for(int i = id; i < (int)num.size(); ++i) {
			if((1 << bit) & num[i].ST) {
				swap(num[i], num[id]);
				any = true;
				break;
			}
		}
		if(any) {
			res.PB(num[id].ST);
			vi tmp = {num[id].ND};
			for(int i = id + 1; i < (int)num.size(); ++i) {
				if(num[i].ST & (1 << bit)) {
					num[i].ST ^= num[id].ST;
					tmp.PB(num[i].ND);
				}
			}
			ans.PB(tmp);
			id++;
		}
	}
	cout << id << "\n";
	for(int i = 0; i < id; ++i) {
		cout << res[i] << " " << (int)ans[i].size() << " ";
		for(auto x : ans[i]) cout << x << " ";
		cout << "\n";
	}
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6724 KB Output is correct
2 Correct 36 ms 6960 KB Output is correct
3 Correct 9 ms 3660 KB Output is correct
4 Correct 8 ms 3788 KB Output is correct
5 Correct 69 ms 11648 KB Output is correct
6 Correct 66 ms 10308 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4480 KB Output is correct
2 Correct 18 ms 4636 KB Output is correct
3 Correct 19 ms 5324 KB Output is correct
4 Correct 25 ms 5752 KB Output is correct
5 Correct 60 ms 10292 KB Output is correct
6 Correct 35 ms 7356 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 7492 KB Output is correct
2 Correct 54 ms 10052 KB Output is correct
3 Correct 2 ms 2672 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 9568 KB Output is correct
2 Correct 113 ms 15812 KB Output is correct
3 Correct 3 ms 2764 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 8260 KB Output is correct
2 Correct 62 ms 9948 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 10684 KB Output is correct
2 Correct 36 ms 7312 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 9716 KB Output is correct
2 Correct 89 ms 13456 KB Output is correct
3 Correct 56 ms 10196 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 13660 KB Output is correct
2 Correct 138 ms 18016 KB Output is correct
3 Correct 121 ms 17124 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4812 KB Output is correct
2 Correct 30 ms 6548 KB Output is correct
3 Correct 75 ms 12452 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 10564 KB Output is correct
2 Correct 49 ms 8332 KB Output is correct
3 Correct 123 ms 16260 KB Output is correct