oj.uz

답안 #218510

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
218510 2020-04-02T08:43:38 Z quocnguyen1012 Praktični (COCI18_prakticni) C++14
0 / 130
 190 ms 22756 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, 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 (v != p)
			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
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 10864 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 7804 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 70 ms 12580 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 86 ms 15344 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 70 ms 13548 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 149 ms 18148 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 118 ms 16160 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 190 ms 22756 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 8816 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 129 ms 17508 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -