oj.uz

Submission #218517

# Submission time Handle Problem Language Result Execution time Memory
218517 2020-04-02T08:47:46 Z quocnguyen1012 Praktični (COCI18_prakticni) C++14
130 / 130
 197 ms 20968 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(){
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
	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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 9968 KB Output is correct
2 Correct 46 ms 9848 KB Output is correct
3 Correct 18 ms 6528 KB Output is correct
4 Correct 15 ms 6656 KB Output is correct
5 Correct 87 ms 14960 KB Output is correct
6 Correct 92 ms 13680 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 7420 KB Output is correct
2 Correct 25 ms 7804 KB Output is correct
3 Correct 30 ms 8444 KB Output is correct
4 Correct 33 ms 8820 KB Output is correct
5 Correct 81 ms 13040 KB Output is correct
6 Correct 53 ms 11636 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 10560 KB Output is correct
2 Correct 80 ms 11756 KB Output is correct
3 Correct 7 ms 5376 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 12660 KB Output is correct
2 Correct 157 ms 17252 KB Output is correct
3 Correct 9 ms 5632 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 11248 KB Output is correct
2 Correct 83 ms 11452 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 13676 KB Output is correct
2 Correct 53 ms 10356 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 12780 KB Output is correct
2 Correct 136 ms 15084 KB Output is correct
3 Correct 79 ms 11632 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 16748 KB Output is correct
2 Correct 197 ms 20968 KB Output is correct
3 Correct 176 ms 20328 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 7932 KB Output is correct
2 Correct 42 ms 8692 KB Output is correct
3 Correct 103 ms 13928 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 13672 KB Output is correct
2 Correct 62 ms 10100 KB Output is correct
3 Correct 144 ms 17252 KB Output is correct