oj.uz

Submission #200090

# Submission time Handle Problem Language Result Execution time Memory
200090 2020-02-05T10:17:42 Z Saboon Praktični (COCI18_prakticni) C++14
130 / 130
 186 ms 19892 KB 
#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){
	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);
		}
		if (h[v] - h[u] > 1)
			a.push_back({par[v] ^ par[u] ^ w, edge.second});
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	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++){
		cout << x[i] << " ";
		cout << ops[i].size() << " ";
		sort(ops[i].begin(), ops[i].end());
		for (auto it : ops[i])
			cout << it + 1 << " ";
		cout << endl;
	}
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 9976 KB Output is correct
2 Correct 43 ms 10104 KB Output is correct
3 Correct 15 ms 6520 KB Output is correct
4 Correct 14 ms 6520 KB Output is correct
5 Correct 89 ms 14968 KB Output is correct
6 Correct 100 ms 14072 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7544 KB Output is correct
2 Correct 22 ms 7544 KB Output is correct
3 Correct 27 ms 8312 KB Output is correct
4 Correct 32 ms 8696 KB Output is correct
5 Correct 98 ms 13788 KB Output is correct
6 Correct 61 ms 10604 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 10744 KB Output is correct
2 Correct 72 ms 12280 KB Output is correct
3 Correct 8 ms 5368 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 13176 KB Output is correct
2 Correct 143 ms 17520 KB Output is correct
3 Correct 9 ms 5496 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 11588 KB Output is correct
2 Correct 82 ms 12172 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 14192 KB Output is correct
2 Correct 45 ms 9724 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 13688 KB Output is correct
2 Correct 123 ms 15600 KB Output is correct
3 Correct 73 ms 12408 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 17652 KB Output is correct
2 Correct 186 ms 19892 KB Output is correct
3 Correct 158 ms 18932 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 8056 KB Output is correct
2 Correct 39 ms 8952 KB Output is correct
3 Correct 99 ms 14532 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 14712 KB Output is correct
2 Correct 57 ms 10744 KB Output is correct
3 Correct 145 ms 18028 KB Output is correct