Submission #218514

#	Time	Username	Problem	Language	Result	Execution time	Memory
218514		quocnguyen1012	Praktični (COCI18_prakticni)	C++14	65 / 130	1095 ms	20100 KiB

parkticni

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10;

vector<pair<int,int> > g[maxn];
int par[maxn], h[maxn], wg[maxn];
vector<pair<int, int> > a;
vector<int> ops[maxn];
int x[maxn];
int t;

void findbase(){
	int n = a.size();
	for (int i = 0; i <= 30; i++){
		bool flag = 0;
		for (int j = t; j < n; j++){
			if (!(a[j].first & (1 << i)))
			   continue;
			swap(a[j], a[t]);
			flag = 1;
			break;
		}
		if (flag == 0)
			continue;
		x[t] = a[t].first;
		for (int j = t; j < n; j++){
			if (a[j].first & (1 << i)){
				ops[t].push_back(a[j].second);
				a[j].first ^= x[t];
			}
		}
		t ++;
	}
}

void dfs(int v, int p = -1){
	for (auto edge : g[v]){
		int u = edge.first, w = wg[edge.second];
		if (h[u] == -1){
			h[u] = h[v] + 1;
			par[u] = par[v] ^ w;
			dfs(u, v);
		}
		if (u != p){
			cerr << u << ' ' << v << '\n';
			a.push_back({par[v] ^ par[u] ^ w, edge.second});
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	#ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
    #endif // LOCAL
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++){
		int v, u;
		cin >> v >> u >> wg[i];
		g[v].push_back({u, i});
		g[u].push_back({v, i});
	}
	memset(h, -1, sizeof h);
	h[1] = 0;
	dfs(1);
	findbase();
	cout << t << endl;
	for (int i = 0; i < t; i++){
        sort(ops[i].begin(), ops[i].end());
		ops[i].erase(unique(ops[i].begin(), ops[i].end()), ops[i].end());
		cout << x[i] << " ";
		cout << ops[i].size() << " ";
		for (auto it : ops[i])
			cout << it + 1 << " ";
		cout << endl;
	}
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 13
• Subtask 3: 13 / 13
• Subtask 4: 0 / 13
• Subtask 5: 13 / 13
• Subtask 6: 0 / 13
• Subtask 7: 13 / 13
• Subtask 8: 0 / 13
• Subtask 9: 13 / 13
• Subtask 10: 0 / 13