이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define inf 2e9
//#define ff first
//#define ss second
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
struct obj{
int ff, ss, ind;
obj(){
ff = ss = ind = 0;
}
obj(int a, int b, int c){
ff = a, ss = b, ind = c;
}
};
const int N = 100000 + 3;
int n, m, p[N], w[N], nm[N], r[32][32], pr[32], ch[32], us[32];
vector <vector <obj> > v;
vector <obj> ed;
bitset <10> bs[32];
void dfs(int x, int pr){
p[x] = 1;
for (auto u: v[x]){
if (u.ff == pr) continue;
if (p[u.ff]) {
ed.push_back(obj(x, u.ff, u.ind));
continue;
}
w[u.ff] = w[x] ^ u.ss;
dfs(u.ff, x);
}
}
void add(int x, int ind){
for (int i = 0; i < 32; i++)
if (x&(1LL<<i))
bs[i][ind] = 1;
}
int get_anc(int x){
if (pr[x] == x) return x;
return pr[x] = get_anc(pr[x]);
}
void unite(int x, int y){
x = get_anc(x), y = get_anc(y);
if (x == y) return;
pr[x] = y;
ch[y] |= ch[x];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif // LOCAL
cin >> n >> m;
v.resize(n);
for (int i = 0; i < m; i++){
int x, y, c;
cin >> x >> y >> c;
--x; --y;
v[x].push_back(obj(y, c, i));
v[y].push_back(obj(x, c, i));
nm[i] = c;
}
// return 0;
dfs(0,-228);
int i = 0;
for (auto u: ed){
int x = u.ff, y = u.ss, ind = u.ind;
int xr = w[x] ^ w[y];
add(w[x]^w[y]^nm[ind], ind);
++i;
}
for (int i = 0; i < 32; i++){
pr[i] = i; ch[i] = (1LL<<i);
}
for (int i = 0; i < 32; i++){
if (!bs[i].any()) continue;
for (int j = 0; j < 32; j++){
if (i == j) continue;
if (!bs[j].any()) continue;
if (bs[i] == bs[j])
unite(i, j);
}
}
// cout << bs[0] << "\n";
// cout << bs[1] << "\n";
// cout << bs[2] << "\n";
// cout << bs[3] << "\n";
vector <int> ans;
for (int i = 0; i < 32; i++){
if (!bs[i].any()) continue;
int cur = get_anc(i);
if (us[cur]) continue;
us[cur] = 1;
ans.push_back(cur);
}
cout << ans.size() << "\n";
for (auto u: ans){
cout << ch[u] << " " << bs[u].count() << " ";
// cout << bs[u] << "!\n";
for (int i = 0; i < m; i++)
if (bs[u][i]) cout << i + 1 << " ";
cout << "\n";
}
}
/**
5 6
1 2 1
2 3 2
1 4 1
4 5 2
1 3 0
1 5 0
*/
컴파일 시 표준 에러 (stderr) 메시지
parkticni.cpp: In function 'int main()':
parkticni.cpp:80:13: warning: unused variable 'xr' [-Wunused-variable]
int xr = w[x] ^ w[y];
^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |