oj.uz

답안 #463445

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
463445 2021-08-11T07:15:58 Z grt Praktični (COCI18_prakticni) C++17
26 / 130
 115 ms 14968 KB 
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 100 * 1000 + 10, mod = 1e9 + 7, p = 31;
int n, m;
vector<pi>V[nax];
int cost[nax];
bool vis[nax];
int xr[nax];
vector<pi>num;
bool done[nax];

void dfs(int x, int par) {
	vis[x] = true;
	for(auto nbh : V[x]) if(nbh.ST != par) {
		if(!vis[nbh.ST]) {
			xr[nbh.ST] = xr[x] ^ cost[nbh.ND];
			dfs(nbh.ST, x);
		} else {
			if(done[nbh.ND]) continue;
			done[nbh.ND] = true;
			num.emplace_back(xr[x] ^ xr[nbh.ST] ^ cost[nbh.ND], nbh.ND);
		}
	}
}

map<int, vi>sc;

int main() {_
	cin >> n >> m;
	for(int a, b, c, i = 1; i <= m; ++i) {
		cin >> a >> b >> c;
		V[a].emplace_back(b, i);
		V[b].emplace_back(a, i);
		cost[i] = c;
	}
	dfs(1, 0);
	for(int bit = 0; bit < 31; ++bit) {
		int hsh = 0;
		for(auto x : num) {
			hsh = ((ll)hsh * p + (((1 << bit) & x.ST) > 0)) % mod;
		}
		if(hsh != 0) sc[hsh].PB(bit);
	}
	cout << (int)sc.size() << "\n";
	for(auto it : sc) {
		int x = 0;
		for(int b : it.ND) x += (1 << b);
		cout << x << " ";
		vi res = {};
		for(auto el : num) {
			if((el.ST & x)) {
				res.PB(el.ND);
			}
		}
		cout << (int)res.size() << " ";
		for(int el : res) cout << el << " ";
		cout << "\n";
	}
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 7628 KB Output is correct
2 Correct 34 ms 7980 KB Output is correct
3 Correct 10 ms 3788 KB Output is correct
4 Correct 9 ms 3884 KB Output is correct
5 Correct 76 ms 13764 KB Output is correct
6 Correct 68 ms 12276 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 4876 KB Output is correct
2 Correct 17 ms 5196 KB Output is correct
3 Correct 20 ms 5848 KB Output is correct
4 Correct 24 ms 6368 KB Output is correct
5 Correct 69 ms 12036 KB Output is correct
6 Correct 41 ms 8400 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 8232 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 77 ms 11460 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 58 ms 9816 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 99 ms 12004 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 76 ms 11556 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 115 ms 14968 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 5444 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 106 ms 12512 KB Too many operations
2 Halted 0 ms 0 KB -