oj.uz

답안 #218514

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
218514 2020-04-02T08:46:44 Z quocnguyen1012 Praktični (COCI18_prakticni) C++14
65 / 130
 1000 ms 20100 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 (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

# 결과 실행 시간 메모리 Grader output
1 Correct 535 ms 11244 KB Output is correct
2 Correct 501 ms 12268 KB Output is correct
3 Correct 177 ms 6904 KB Output is correct
4 Correct 106 ms 7160 KB Output is correct
5 Correct 829 ms 19304 KB Output is correct
6 Correct 831 ms 17640 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 312 ms 8052 KB Output is correct
2 Correct 320 ms 8976 KB Output is correct
3 Correct 293 ms 9716 KB Output is correct
4 Correct 380 ms 10480 KB Output is correct
5 Execution timed out 1008 ms 17508 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 521 ms 12016 KB Output is correct
2 Correct 709 ms 14952 KB Output is correct
3 Correct 9 ms 5376 KB Output is correct

Subtask #4
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 856 ms 14700 KB Output is correct
2 Execution timed out 1086 ms 18412 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 697 ms 13160 KB Output is correct
2 Correct 782 ms 14628 KB Output is correct

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1060 ms 17128 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 840 ms 14972 KB Output is correct
2 Correct 911 ms 20100 KB Output is correct
3 Correct 701 ms 15104 KB Output is correct

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1095 ms 19000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 305 ms 8504 KB Output is correct
2 Correct 364 ms 10356 KB Output is correct
3 Correct 878 ms 18212 KB Output is correct

Subtask #10
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 985 ms 16300 KB Output is correct
2 Correct 545 ms 12660 KB Output is correct
3 Execution timed out 1062 ms 18088 KB Time limit exceeded